Python上的时间复杂度
Page content
在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。 这是一个代表算法输入值的字符串的长度的函数。
想必大家都听过下面这么一段话，但要把这个当真理，那恐怕很容易写出效率不高的代码。
在编程过程中，不同的数据代表着不一样的作用，并且他们的执行效率也会不一样。
0x00 大O表示法
大O符号，又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个函数来描述一个函数数量级的渐近上界。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
这里简单通过一张图来说明下他们的关系。
而后我们将逐一介绍python3中的常见对容器的操作效率之分。
0x00 List列表
列表应该是我们用到最为频繁的对象类型了
| 操作 | 案例 | 类型 | 备注 |
|---|---|---|---|
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | |
| Pop | l.pop() | O(1) | l.pop(-1) 同理 |
| Clear | l.clear() | O(1) | l = [] 同理 |
| Slice | l[a:b] | O(b-a) | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N) |
| Extend | l.extend(…) | O(len(…)) | 取决于…的长度 |
| Construction | list(…) | O(len(…)) | 取决于…的长度 |
| Insert | l.insert(1) | O(N) | |
| Pop | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) (see above) |
| check ==, != | l1 == l2 | O(N) | |
| Insert | l[a:b] = … | O(N) | |
| Delete | del l[i] | O(N) | 取决于i的位置，最坏的情况为O(N) |
| Containment | x in/not in l | O(N) | 需逐个查找导致 |
| Copy | l.copy() | O(N) | l[:] 同理 |
| Remove | l.remove(…) | O(N) | |
| Extreme value | min(l)/max(l) | O(N) | 需逐个查找导致 |
| Reverse | l.reverse() | O(N) | |
| Iteration | for v in l: | O(N) | 当循环中没有return或break的时候，为O(N) |
| Sort | l.sort() | O(N Log N) | |
| Multiply | k*l | O(k N) |
0x01 Set集合
大部分set操作的时间复杂度都为O(1)
| 操作 | 案例 | 类型 | 备注 |
|---|---|---|---|
| Length | len(s) | O(1) | |
| Add | s.add(5) | O(1) | |
| Containment | x in/not in s | O(1) | 对比 list/tuple 的O(N) 快很多 |
| Remove | s.remove(..) | O(1) | compare to list/tuple - O(N) |
| Discard | s.discard(..) | O(1) | |
| Pop | s.pop() | O(1) | popped value “randomly” selected |
| Clear | s.clear() | O(1) | 与 s = set() 同理 |
| Construction | set(…) | O(len(…)) | 取决于 … 的长度 |
| check ==, != | s != t | O(len(s)) | 与len(t)同理 |
| <=/< | s <= t | O(len(s)) | 类似issubset方法 |
| >=/> | s >= t | O(len(t)) | |
| Union | s | t | O(len(s)+len(t)) | |
| Intersection | s & t | O(len(s)+len(t)) | |
| Difference | s - t | O(len(s)+len(t)) | |
| Symmetric Diff | s ^ t | O(len(s)+len(t)) | |
| Iteration | for v in s: | O(N) | 当循环中没有return或break的时候，为O(N) |
| Copy | s.copy() | O(N) |
0x02 dict字典及defaultdict默认字典
可以看到大部分的dict操作也是O(1)
| 操作 | 案例 | 类型 | 备注 |
|---|---|---|---|
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| get/setdefault | d.get(k) | O(1) | |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | |
| Clear | d.clear() | O(1) | 与 s = {} 或 s = dict() 同理 |
| View | d.keys() | O(1) | 与 d.values() 同理 |
| Construction | dict(…) | O(len(…)) | |
| Iteration | for k in d: | O(N) | 包含以下方法： keys, values, items |
0x03 collections.deque双向队列
这个东西有点像list 但显然比list好用多了
| 操作 | 案例 | 类型 | 备注 |
|---|---|---|---|
| Copy | dq.copy() | O(n) | |
| append | dq.append(5) | O(1) | |
| appendleft | dq.appendleft(1) | O(1) | 作用相当于 list.insert(0,1), 但后者效率为O(N) |
| pop | dq.pop() | O(1) | |
| popleft | dq.popleft() | O(1) | |
| extend | dq.extend(k) | O(len(k)) | |
| extendleft | dq.extendleft(k) | O(len(k)) | |
| rotate | dq.rotate(k) | O(len(k)) | |
| remove | dq.remove(1) | O(n) |
当然，类似item in/not in set(list)这样的操作并没有多大的意义，在时间复杂度上任然是O(len(list))。即便set的成员对象判断上为O(1),但把list转换为set的过程已经是个取决于list长度的操作了。
引自 https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
