python中各种 *** 作的时间复杂度

概述以下的python *** 作的时间复杂度是Cpython解释器中的。其它的Python实现的可能和接下来的有稍微的不同。 一般来说,“n”是目前在容器的元素数量。 “k”是一个参数的值或参数中的元素的数量。

以下的python *** 作的时间复杂度是cpython解释器中的。其它的Python实现的可能和接下来的有稍微的不同。

一般来说,“n”是目前在容器的元素数量。 “k”是一个参数的值或参数中的元素的数量。

（1）列表：List@H_404_8@@H_404_8@

一般情况下，假设参数是随机生成的。

在内部，列表表示为数组。在内部，列表表示为数组。 最大的成本来自超出当前分配大小的范围（因为一切都必须移动），或者来自在开始处附近插入或删除某处（因为之后的所有内容都必须移动）。 如果需要在两端添加/删除，请考虑改用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@H_404_8@@H_404_8@

双端队列（双端队列）在内部表示为双链表。 （为得到更高的效率，是数组而不是对象的列表。）两端都是可访问的，但即使查找中间也很慢，而向中间添加或从中间删除仍然很慢。

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@H_404_8@@H_404_8@

参考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.@H_404_8@

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@H_404_8@

为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.@H_404_8@@H_404_8@

[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.@H_404_8@@H_404_8@

[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

 

总结

以上是内存溢出为你收集整理的python中各种 *** 作的时间复杂度全部内容，希望文章能够帮你解决python中各种 *** 作的时间复杂度所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。