python数据结构时间复杂度


表格数据来自于python官方网站

列表

Operation Average Case Amortized Worst Case
Copy O(n) O(n)
Append O(1) O(1)
Pop last O(1) O(1)
Pop intermediate O(k) O(k)
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 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)

可以看到最常用的append(尾端添加)、pop(尾端移除)、按下标查找、按下标更新和数组长度操作时间复杂度都是O(1),切片操作是O(n)

字典

Operation Average Case Amortized Worst Case
k in d O(1) O(n)
Copy O(n) O(n)
Get Item O(1) O(n)
Set Item O(1) O(n)
Delete Item O(1) O(n)
Iteration O(n) O(n)

集合

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))

队列

这里的队列指的是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)

文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
指令系统 指令系统
计算机组成原理系列之九
下一篇 
python数据结构之栈 python数据结构之栈
概念栈是线性数据结构的一种,是数据项的有序集合。添加项和移除项都发生在同一端,称为“顶端”,另一端称为“底端”。 因为添加项和移除项都在栈的顶端进行,因此最新添加的项在移除时也会被第一个移除,这种排序原则称为后进先出(LIFO),这意味着越
2020-07-24
  目录