共计 1250 个字符，预计需要花费 4 分钟才能阅读完成。
算法复杂度分为时间复杂度和空间复杂度。时间复杂度 是指程序要执行的次数，而非执行时间；而 空间复杂度 是指算法执行过程中大概所占用的最大内存空间。计算机资源最重要的是时间和空间 (即寄存器) 资源，因此复杂度分为时间和空间复杂度。
大 O 表示法
大 O 时间复杂度表示法：T(n)=O(f(n))。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
常见的大 O 数量级函数：
| f(n) | 名称 |
|---|---|
| 1 | 常数 |
| log(n) | 对数 |
| n | 线性 |
| n*log(n) | 对数线性 |
| n² | 平方 |
| n³ | 立方 |
| 2ⁿ | 指数 |
列表常用操作性能
按索引取值和赋值（v=a[i]，a[i]=v），由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为 O(1)。
列表增长：lst.append(v)，执行时间是 O(1)；lst= lst+[v]，执行时间是 O(n+k)，其中 k 是被加的列表长度。
4 种生成 n 个整数列表的方法：
from timeit import Timer
def t1():
lst = []
for i in range(1000):
lst = lst + [i]
def t2():
lst = []
for i in range(1000):
lst.append(i)
def t3():
lst = [i for i in range(1000)]
def t4():
lst = list(range(1000))
time1 = Timer("t1()", "from __main__ import t1")
print("concat:\t\t{} seconds".format(time1.timeit(1000)))
time2 = Timer("t2()", "from __main__ import t2")
print("append:\t\t{} seconds".format(time2.timeit(1000)))
time3 = Timer("t3()", "from __main__ import t3")
print("comprehension:\t{} seconds".format(time3.timeit(1000)))
time4 = Timer("t4()", "from __main__ import t4")
print("list range:\t{} seconds".format(time4.timeit(1000)))可以看到，4 种方法运行时间差别挺大的，列表连接（+）最慢，中间的是 append 和列表推导式，List range 最快。
字典常用操作性能
与列表不同，字典是根据键值（key）找到数据项，而列表是根据索引（index）。最常用的取值和赋值，其性能均为 O(1)。另一个重要操作 contains(in)是判断字典中是否存在某个键值（key），这个性能也是 O(1)。
更多 Python 数据类型操作复杂度可参考官方文档：https://wiki.python.org/moin/TimeComplexity
正文完
