|
以下的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))
|
? |
-
As seen in the?source code?the complexities for set difference s-t or s.difference(t) (set_difference()) and in-place set difference s.difference_update(t) (set_difference_update_internal()) are different! The first one is O(len(s)) (for every element in s add it to the new set,if not in t). The second one is O(len(t)) (for every element in t remove it from s). So care must be taken as to which is preferred,depending on which one is the longest set and whether a new set is needed.
- To perform set operations like s-t,both s and t need to be sets. However you can do the method equivalents even if t is any iterable,for example s.difference(l),where l is a list.
（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)
|
Notes
[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.
?
参考：https://wiki.python.org/moin/TimeComplexity
? （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
