Python 各种集合内置方法的时间复杂度

电玩女神 2022-11-30 15:53 155阅读 0赞

转载来源：[https://blog.csdn.net/Baoli1008/article/details/48059623][https_blog.csdn.net_Baoli1008_article_details_48059623]

# Python内置方法的时间复杂度 #

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

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

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

### 一、列表（`list`） ###

以完全随机的列表考虑平均情况。

列表是以数组（Array）实现的。最大的开销发生在超过当前分配大小的增长，这种情况下所有元素都需要移动；或者是在起始位置附近插入或者删除元素，这种情况下所有在该位置后面的元素都需要移动。如果你需要在一个队列的两端进行增删的操作，应当使用`collections.deque`（双向队列）

<table> 
 <thead> 
  <tr> 
   <th>col 1</th> 
   <th>col 2</th> 
   <th>col 3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>平均情况</td> 
   <td><a href="http://en.wikipedia.org/wiki/Amortized_analysis" rel="nofollow">最坏情况</a></td> 
  </tr> 
  <tr> 
   <td>复制copy()</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>append(item) [注1]</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>插入元素：insert(i, item)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>取元素list[i]</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>更改元素list[i]</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>删除元素：pop(i)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>删除最后一个元素：pop()</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>遍历</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>取切片</td> 
   <td>O(k)</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>删除切片</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>更改切片</td> 
   <td>O(k+n)</td> 
   <td>O(k+n)</td> 
  </tr> 
  <tr> 
   <td>extend[注1]</td> 
   <td>O(k)</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td><a href="https://juejin.im/entry/6844903480931385358" rel="nofollow">排序（Timsort）</a></td> 
   <td>O(n log n)</td> 
   <td>O(n log n)</td> 
  </tr> 
  <tr> 
   <td>列表乘法</td> 
   <td>O(nk)</td> 
   <td>O(nk)</td> 
  </tr> 
  <tr> 
   <td>x in s</td> 
   <td>O(n)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>min(s), max(s)</td> 
   <td>O(n)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>计算长度 len()</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

### 二、双向队列（`collections.deque`） ###

deque （double-ended queue，双向队列）是以双向链表的形式实现的 (Well, a list of arrays rather than objects, for greater efficiency)。双向队列的两端都是可达的，但从查找队列中间的元素较为缓慢，增删元素就更慢了。

<table> 
 <thead> 
  <tr> 
   <th>col 1</th> 
   <th>col 2</th> 
   <th>col 3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>平均情况</td> 
   <td>最坏情况</td> 
  </tr> 
  <tr> 
   <td>复制</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>append</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>appendleft</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>popleft</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>extend</td> 
   <td>O(k)</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>extendleft</td> 
   <td>O(k)</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>rotate</td> 
   <td>O(k)</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>remove</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

### 三、集合（`set`） ###

内部实现是dict的。在in操作上是O(1), 这一点比list要强。  
未列出的操作可参考 dict —— 二者的实现非常相似。

<table> 
 <thead> 
  <tr> 
   <th>col 1</th> 
   <th>col 2</th> 
   <th>col 3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>平均情况</td> 
   <td>最坏情况</td> 
  </tr> 
  <tr> 
   <td>x in s</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>并集 s</td> 
   <td>t</td> 
   <td>O(len(s)+len(t))</td> 
  </tr> 
  <tr> 
   <td>交集 s&amp;t</td> 
   <td>O(min(len(s), len(t))</td> 
   <td>O(len(s) * len(t))</td> 
  </tr> 
  <tr> 
   <td>差集 s-t</td> 
   <td>O(len(s))</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>s.difference_update(t)</td> 
   <td>O(len(t))</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>对称差集 s^t</td> 
   <td>O(len(s))</td> 
   <td>O(len(s) * len(t))</td> 
  </tr> 
  <tr> 
   <td>s.symmetric_difference_update(t)</td> 
   <td>O(len(t))</td> 
   <td>O(len(t) * len(s))</td> 
  </tr> 
  <tr> 
   <td>删除元素remove(item)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>插入元素 add(item)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

由源码得知，求差集（`s-t`，或`s.difference(t)`）运算与更新为差集（`s.difference_uptate(t)`）运算的时间复杂度并不相同！前者是将在s中，但不在t中的元素添加到新的集合中，因此时间复杂度为O(len(s))；后者是将在t中的元素从s中移除，因此时间复杂度为O(len(t))。因此，使用时请留心，根据两个集合的大小以及是否需要新集合来选择合适的方法。

集合的s-t运算中，并不要求t也一定是集合。只要t是可遍历的对象即可。

### 四、字典（`dict`） ###

下列字典的平均情况基于以下假设：

1.  对象的散列函数足够撸棒（robust），不会发生冲突。
2.  字典的键是从所有可能的键的集合中随机选择的。

小窍门：只使用字符串作为字典的键。这么做虽然不会影响算法的时间复杂度，但会对常数项产生显著的影响，这决定了你的一段程序能多快跑完。

<table> 
 <thead> 
  <tr> 
   <th>col 1</th> 
   <th>col 2</th> 
   <th>col 3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>平均情况</td> 
   <td>最坏情况</td> 
  </tr> 
  <tr> 
   <td>复制copy() [注2]</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>插入元素 dict[k]</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>取元素get(k)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>key in dict</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>dict[k] 更改元素 [注1]</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>删除元素pop(k)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>keys(), values, items() 遍历[注2]</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

### 五、堆（`heap`） ###

import heapq

Python 3的`heapq`建立的是最小堆；若想建立最大堆，可以在插入数据之前，先把数据取反（即乘上 -1），在弹出数据之后，再把数据取反（即乘上 -1）即可。

> heap = \[-3, -1, 5, 6, 3\]

<table> 
 <thead> 
  <tr> 
   <th>col 1</th> 
   <th>col 2</th> 
   <th>col 3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>平均情况</td> 
   <td>最坏情况</td> 
  </tr> 
  <tr> 
   <td>复制copy() [注2]</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>建堆heapq.heapify(heap)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>插入元素 heapq.heappush(heap， item)</td> 
   <td>O(logn)</td> 
   <td>O(logn)</td> 
  </tr> 
  <tr> 
   <td>返回根元素heap[0]</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>返回并删除根元素heapq.heappop(heap)</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

> `heapq.heappushpop(heap, item) 将 item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。`

注：  
\[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.

[https_blog.csdn.net_Baoli1008_article_details_48059623]: https://blog.csdn.net/Baoli1008/article/details/48059623
[Python Wiki]: https://wiki.python.org/moin/TimeComplexity
[GPL v2]: http://moinmo.in/GPL