数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

第一讲 时间复杂度、特殊矩阵的存储和压缩

一、时间、空间复杂度

​ 只考虑次数,不考虑常数。常见复杂度有:O(1)、O(n)、O(n^k)、O(logn)、O(nlogn)
​ 考题:2011-1、2012-1、2013-1、2014-1、2017-1、2019-1

2011-1 A

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2013-1 D

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2014-1 C

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2017-1 B

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2019-1 B

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

二、特殊矩阵的存储和压缩

​ 矩阵的按行展开、按列展开,展开后下标从0开始。

按行展开

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

按列展开

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

​ 考题:2016-4、2018-3、2020-1

2016-4 B

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2+3*28+2 = 88 88-1 = 87

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2018-3 A

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

12+11+10+9+8 + 1 = (8+12)*5/2 + 1 = 51

51-1 = 50;

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

2020-1

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

1+2+3+4+5+6 + 2 = (1+6)*6/2 +2 = 23

23-1 = 22 ;

数据结构_第一讲 时间复杂度、特殊矩阵的存储和压缩

上一篇:TSP问题求解(动态规划法、分支限界法、回溯法)


下一篇:python 数组 冒泡排序