上一篇文章《算法是什么》中提到,解决同一个问题,可能会有多种算法,但程序的好坏,一般用复杂度来衡量。本文介绍算法中的两个基本衡量标准:时间复杂度、空间复杂度。

时间复杂度

时间复杂度,是用来评估算法运行效率的一个式子。一般来说,时间复杂度高的算法,比复杂度低的算法慢。一般记作O(x),O后面的内容,可以理解为是一个单位。类比生活中的:分钟、小时、天。

常见的时间复杂度(按效率排序):

O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2) < O(n^2log(n)) < O(n^3)

复杂问题的时间复杂度:

O(n!)  O(2^n)  O(n^n)

常见时间复杂度示例

# O(1)
print('Hello World')

# O(n)
for i in range(n):
     print('Hello World')

# O(n^2)
for i in range(n):
     for j in range(n):
         print('Hello World')

# O(log(n)) 或者O(log(n))
while n>1: 
    print(n)
    n = n // 2

例如:n=64
输出:64  32  16  8  4  2
2的6次方=64   log2(64) = 6

判断时间复杂度步骤:

1) 确定问题规模n

2) 循环减半过程 log(n)

3) k层关于n的循环 n^k

空间复杂度

空间复杂度,是用来评估算法内存占用大小的式子,空间复杂度表示方法和时间复杂度完全一样。

判断方法:

1) 算法使用了几个变量:O(1)

2) 算法使用了长度为n的一维列表:O(n)

3) 算法使用了m行n列的二维列表:O(m*n)

多数场景中,挑选 "好" 算法往往更注重的是时间复杂度,空间复杂度只要处于一个合理的范围即可。

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/72