算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指程序要执行的次数，而非执行时间；而空间复杂度是指算法执行过程中大概所占用的最大内存空间。计算机资源最重要的是时间和空间(即寄存器)资源，因此复杂度分为时间和空间复杂度。

大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