时间复杂度和空间复杂度

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

时间复杂度

时间复杂度，是用来评估算法运行效率的一个式子。一般来说，时间复杂度高的算法，比复杂度低的算法慢。一般记作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)

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