本文主要是介绍python数据格式操作的时间复杂度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
list
python的列表内部实现是数组(具体实现要看解析器, CPython的实现 ),因此就有组数的特点。超过容量会增加更多的容量,set, get 是O(1),但del, insert, in的性能是O(n)。具体的看下表,'n’是容器中当前的元素数, 'k’需要操作的元素个数
Operation | Average Case | Amortized Worst Case |
---|---|---|
Copy | O(n) | O(n) |
Append[1] | O(1) | O(1) |
Insert | O(n) | O(n) |
Get Item | O(1) | O(1) |
Set Item | O(1) | O(1) |
DeleteItem | 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) |
dict
关于字典需要了解的是hash函数和哈希桶。一个好的hash函数使到哈希桶中的值只有一个,若多个key hash到了同一个哈希桶中,称之为哈希冲突。查找值时,会先定位到哈希桶中,再遍历hash桶。更详细的信息请点这里。在hash基本没有冲突的情况下get, set, delete, in方面都是O(1)。
Operation | Average Case | Amortized Worst Case |
---|---|---|
Copy[2] | O(n) | O(n) |
Get Item | O(1) | O(n) |
Set Item[1] | O(1) | O(n) |
Delete Item | O(1) | O(n) |
x in s | O(1) | O(n) |
Iteration[2] | O(n) | O(n) |
set
内部实现是dict的。在in操作上是O(1), 这一点比list要强。
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) |
原文连接链接:https://www.jianshu.com/p/a8fa3d31aa40
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这篇关于python数据格式操作的时间复杂度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!