第一讲 时间复杂度、特殊矩阵的存储和压缩
一、时间、空间复杂度
只考虑次数,不考虑常数。常见复杂度有: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 ;