极客笔记Python 操作的复杂性快速参考表
时间复杂性是衡量时间的一种方式，确定算法执行所需的时间。它还检查输入大小增加时运行时间的增加情况。时间复杂性用大写字母O表示，它设置了在最坏情况下算法性能的上限。
每当我们设计一个算法时，不仅要考虑正确性，还要考虑时间复杂性和性能特征。
例如，如果一个算法的时间复杂度是O(n)，那么用双倍输入大小执行给定算法将需要O(n)的两倍的时间，而如果我们采用另一个时间复杂度为O(n^2)的算法，该算法将需要O(n^2)的四倍时间来执行双倍输入大小的算法。
列表的时间复杂性
在内部，列表被视为数组。下面是在Python中执行列表操作的时间复杂性快速参考表。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Copy | O(n) | O(n) |
| Append[1] | O(1) | O(1) |
| Pop last | O(1) | O(1) |
| Pop intermediate[2] | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Set Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(k+n) |
| Extend[1] | O(k) | O(k) |
| Sort | O(n log n) | O(n log n) |
| Multiply | O(nk) | O(nk) |
| x in s | O(n) | |
| min(s), max(s) | O(n) | |
| Get Length | O(1) | O(1) |
通常，’n’是当前列表中的元素数量，’k’可以是参数的值或者参数中的元素数量。
Collections.deque
deque是双端队列的缩写，它在内部使用双向链表表示。以下是deque操作的速查表及其时间复杂度。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Copy | O(n) | O(n) |
| append | O(1) | O(1) |
| appendleft | O(1) | O(1) |
| pop | O(1) | O(1) |
| popleft | O(1) | O(1) |
| extend | O(k) | O(k) |
| extendleft | O(k) | O(k) |
| rotate | O(k) | O(k) |
| remove | O(n) | O(n) |
| Get Length | O(1) | O(1) |
集合
以下是集合数据结构操作的作弊表，包括时间复杂度。
| Operation | Average case | Worst Case |
|---|---|---|
| x in s | O(1) | O(n) |
| Union s|t | O(len(s)+len(t)) | |
| Intersection s&t | O(min(len(s), len(t))) | O(len(s) * len(t)) |
| Multiple intersection s1&s2&..&sn | (n-1)*O(l) where l is max(len(s1),..,len(sn)) | |
| Difference s-t | O(len(s)) | |
| s.difference_update(t) | O(len(t)) | |
| Symmetric Difference s^t | O(len(s)) | O(len(s) * len(t)) |
| s.symmetric_difference_update(t) | O(len(t)) | O(len(t) * len(s)) |
字典
下面是字典操作复杂度速查表。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| k in d | O(1) | O(n) |
| Copy[3] | O(n) | O(n) |
| Get Item | O(1) | O(n) |
| Set Item[1] | O(1) | O(n) |
| Delete Item | O(1) | O(n) |
| Iteration[3] | O(n) | O(n) |