时间复杂度与空间复杂度

在学习数据结构与算法的时候,总不免提到时间复杂度以及空间复杂度这两个概念,以及每次对所写代码进行的复杂度分析等。

时间复杂度

时间复杂度描述的是一个算法执行时间与数据规模的增长关系,通常用 T(n) = O(f(n)) 来表示, n 表示数据的规模,f(n) 每行代码执行的次数总和。
这里的重点在于增长关系这几个字,一个算法的时间复杂度,通常只需要考虑 n 的增长规模,这里的 n 指的是每段代码的执行次数,所以时间复杂度大多都只看循环、递归来分析,而与那些常数、系数等无关。

1
2
3
4
5
6
7
8
def calc(n):
sum = 0
i = 1
for i in range(n+1):
sum += i
return sum

print(calc(5))

这段代码可以累加从 0 到 n 的和,我们这样对它进行分析:第 2、3 行代码需要执行一次,第 4、5 行需要执行 n 次,所以它的时间复杂度为 O(n + 2)。但是因为系数、常数这些对 n 的增长规模没有影响(如果是 n² 那就有影响了,都已经到平方阶了),不需要考虑,可以忽略,所以这样看其时间复杂度为 O(n) 。

1
2
3
4
5
6
7
8
9
def calc(n):
sum = 0
i = 1
for i in range(n+1):
for j in range(n+1):
sum += i*j
return sum

print(calc(5))

像这种嵌套了两层 for 循环的代码,两行代码分别执行了 n 遍,并且是嵌套,时间复杂度就是 O(n²)。

1
2
3
4
def calc(n):
return math.log(n)

print(calc(5))

像这样的一段代码里没有循环啊、递归等语句的,通常时间复杂度都是 O(1)。

** 时间复杂度计算小技巧 **
1、如果没有循环或递归,都是常量级的代码,时间复杂度就是 O(1)
2、只关注循环次数最多的一段代码,它的量级就可作为整段代码的时间复杂度
3、如果是for循环嵌套的代码,采用乘法计算其内外复杂度;如果是一个函数里有多段代码,则分析出每一段代码的时间复杂度,在将它们相加,最后去掉系数以及常数,取最大量级的作为整段代码的时间复杂度。例如,O(2n²+n+2) 可简化为 O(n²)。

空间复杂度

类比时间复杂度,空间复杂度的概念在几个字上不一样,完整表述为:描述一个算法占用空间与数据规模的增长关系。

1
2
3
4
5
6
7
8
def calc(n):
i = 1
result = np.zeros(n)
for i in range(n):
result[i] += i*i
return result

print(calc(5))

第二行代码申请了存储空间 i,但它是常量阶的,跟数据的增长规模没有关系,所以不用理;第三行代码申请了一个容量为 n 的数组,剩下的代码都没有涉及到占用空间了,所以整段代码的空间复杂度为 O(n) 。

常见的复杂度

常见的复杂度从低阶到高阶有:O(1)、O(logn)、O(n)、O(nlogn)、O(n²)

0%