算法分析

时间空间复杂度

程序和算法不同，其执行的时间和占用的空间也不同，如何比较两种算法的优劣呢？引入大 \(O\) 记法进行算法复杂度的评价。

\(f(n)\)	名称
\(1\)	常数
\(logn\)	对数
\(n\)	线性
\(nlogn\)	对数线性
\(n^2\)	平方
\(n^3\)	立方
\(2^n\)	指数

【举例】

1. 常数 \(O(1)\)

n = 1024
m = 512
z = n + m
print(z)

变量的变化并不影响执行指令的条数，此时复杂度为\(O(1)\)，与数据输入的规模无关

2. 对数 \(O(logn)\)

i = 1
while(i < n):
    i = i * 2

\(2^k = n, k = logn(以2为低)\)，此时，执行\(1+logn\) 次，算法复杂度为\(logn\)

3. 线性 \(O(n)\)

sum = 0
for i in range(n):
    sum += i

循环体内按步长1循环，循环一轮，也即 \(n\) 次

4. 对数线性 \(O(nlogn)\)

i = 1
for i in range(n):
    while(i < n):
        i = i * 2

内层为对数，外层为线性

5. 平方 \(O(n^2)\)

sum = 0
for i in range(n):
    for j in range(n):
        sum += j

两层 \(n\) 次循环，一般用于二维数组

6. 立方 \(O(n^3)\)

sum = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            sum += k

三层 \(n\) 次循环

7. 指数 \(O(2^n)\)

def f(n):
    if n < 3:
        return 1
    else:
        return f(n-2) + f(n-1)

上述为求解第 \(n\) 个斐波那契数列的递归算法，如图所示为求解\(f(5)\)，当\(n-∞\) 时，复杂度为\(2^n\)

Python数据结构的性能

列表

Python中关于列表的基本操作，如果生成一个长为n的列表，有以下四种常见的操作：

# 通过连接创建列表
def test1():
    l = []
    for i in range(n):
        l = l + [i]
# 通过追加方式
def test2():
    l = []
    for i in range(n):
        l.append(i)
# 列表解析式
def test3():
    l = [i for i in range(n)]
# 列表构造器
def test4():
    l = list(range(n))

此时可以看出，不同的列表创建方式，其执行的效率有着数量级的变化。同样的，可以使用Timer进行pop的性能分析。下表为Python中列表操作的复杂度值：

字典

注意，判断某个值是否在字典中的复杂度为\(O(1)\)，时间不会随着字典长度变大而边长，但是对于列表，其复杂度为\(O(n)\)，时间会随着列表的增大而增大。

讨论题

1. \(O(n^2)\)
2. \(O(n)\)
3. \(O(n)\)
4. \(O(n^3)\)
5. \(O(n)\)
6. \(O(n)\)