以下的python操作的时间复杂度是Cpython解释器中的。其它的Python实现的可能和接下来的有稍微的不同。
一般来说,“n”是目前在容器的元素数量。 “k”是一个参数的值或参数中的元素的数量。
（1）列表：List
一般情况下，假设参数是随机生成的。
在内部，列表表示为数组。在内部，列表表示为数组。 最大的成本来自超出当前分配大小的范围（因为一切都必须移动），或者来自在开始处附近插入或删除某处（因为之后的所有内容都必须移动）。 如果需要在两端添加/删除，请考虑改用collections.deque。
| 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) |
（2）双端队列：collections.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) |
（3）集合：set
参考dict，故意实现很相似。
| Operation | Average case | Worst Case | notes |
| 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)) | replace "min" with "max" if t is not a set |
| 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)) |
（4）子字典：dict
为dict对象列出的平均情况时间假设对象的哈希函数足够强大，以至于不常见冲突。 平均情况假设参数中使用的键是从所有键集中随机选择的。
请注意，有一种快速的命令可以（实际上）仅处理str键。 这不会影响算法的复杂性，但是会显着影响以下恒定因素：典型程序的完成速度。
| 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) |
[1] = These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container.
[2] = Popping the intermediate element at index k from a list of size n shifts all elements after k by one slot to the left using memmove. n - k elements have to be moved, so the operation is O(n - k). The best case is popping the second to last element, which necessitates one move, the worst case is popping the first element, which involves n - 1 moves. The average case for an average value of k is popping the element the middle of the list, which takes O(n/2) = O(n) operations.
[3] = For these operations, the worst case n is the maximum size the container ever achieved, rather than just the current size. For example, if N objects are added to a dictionary, then N-1 are deleted, the dictionary will still be sized for N objects (at least) until another insertion is made.
湘公网安备 43102202000103号