Python内置方法的时间复杂度

转载自：http://www.orangecube.NET/Python-time-complexity

本文翻译自Python Wiki
本文基于GPL v2协议，转载请保留此协议。

本页面涵盖了Python中若干方法的时间复杂度（或者叫“大欧”，“Big O”）。该时间复杂度的计算基于当前（译注：至少是2011年之前）的CPython实现。其他Python的实现（包括老版本或者尚在开发的CPython实现）可能会在性能表现上有些许小小的差异，但一般不超过一个O(log n)项。

本文中，’n’代表容器中元素的数量，’k’代表参数的值，或者参数的数量。

最坏情况 复制 O(n) O(n) append[注1] O(1) O(1) 插入 O(n) O(n) 取元素 O(1) O(1) 更改元素 O(1) O(1) 删除元素 O(n) O(n) 遍历 O(n) O(n) 取切片 O(k) O(k) 删除切片 O(n) O(n) 更改切片 O(k+n) O(k+n) extend[注1] O(k) O(k) 排序 O(n log n) O(n log n) 列表乘法 O(nk) O(nk) x in s O(n)   min(s), max(s) O(n)   计算长度 O(1) O(1)

算法的时间复杂度，但会对常数项产生显著的影响，这决定了你的一段程序能多快跑完。

操作	平均情况	最坏情况
复制[注2]	O(n)	O(n)
取元素	O(1)	O(n)
更改元素[注1]	O(1)	O(n)
删除元素	O(1)	O(n)
遍历[注2]	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] = 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.