马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
Python 列表、双向队列、集合、字典的时间复杂度
文章翻译自 -> https://wiki.python.org/moin/TimeComplexity
这篇文章记录了目前 CPython 中各种操作的时间复杂度（也称为 "Big O" 或 "Big Oh"）。
其他 Python 实现（或者旧的或正在开发中的 CPython 版本）可能有稍微不同的性能特性。
然而，我们通常可以安全地假设它们的效率不会超过 O(log n)。
通常情况下，'n' 是目前容器中的元素数量。'k' 是参数的值或参数中的元素数量。
list（列表）
平均情况假设参数均匀且随机地生成。
在内部，列表将被表示为一个数组：最大的代价来自于超出当前的分配大小（因为所有的元素都必须进行移动），或者在接近起点的地方进行插入或删除操作（因为随后的所有元素都必须进行移动）。
如果你需要频繁地在两端添加或删除元素，可以考虑使用 collections.deque。
以下是列表各种操作的时间复杂度：
操作 | 平均时间复杂度 | 最坏时间复杂度 | | 复制 | O(n) | O(n) | | 追加（注1） | O(1) | O(1) | | 弹出最后一个元素 | O(1) | O(1) | | 弹出中间元素（注2） | O(n) | O(n) | | 插入 | O(n) | O(n) | | 获取元素 | O(1) | O(1) | | 设置元素 | O(1) | O(1) | | 删除元素 | O(n) | O(n) | | 迭代 | O(n) | O(n) | | 获取切片 | O(k) | O(k) | | 删除切片 | O(n) | O(n) | | 设置切片 | O(k+n) | O(k+n) | | 扩展（注1） | O(k) | O(k) | | 排序 | O(n log n) | O(n log n) | | 乘法 | O(nk) | O(nk) | | x in s | O(n) |
| | min(s), max(s) | O(n) |
| | 获取长度 | O(1) | O(1) |
collections.deque（双向队列）
在内部，双向队列被表示为一个双向链表（实际上是数组的列表，而非对象，以提高效率）：两端都可以进行访问，但即便如此，查找中间的元素也很慢，而且在中间添加或删除元素会更慢。
以下是双向队列各种操作的时间复杂度：
操作 | 平均时间复杂度 | 最坏时间复杂度 | | 复制 | O(n) | O(n) | | 追加 | O(1) | O(1) | | 左侧追加 | O(1) | O(1) | | 弹出 | O(1) | O(1) | | 左侧弹出 | O(1) | O(1) | | 扩展 | O(k) | O(k) | | 左侧扩展 | O(k) | O(k) | | 旋转 | O(k) | O(k) | | 删除 | O(n) | O(n) | | 获取长度 | O(1) | O(1) |
set（集合）
参见 dict（字典，见下方）-- 它们的实现有意设计得很相似。
以下是集合的各种操作的时间复杂度：
操作 | 平均时间复杂度 | 最坏时间复杂度 | 备注 | | x in s | O(1) | O(n) | | | 并集 s|t | O(len(s)+len(t)) | | | | 交集 s&t | O(min(len(s), len(t))) | O(len(s) * len(t)) | 如果 t 不是集合，将 "min" 替换为 "max" | | 多个交集 s1&s2&...&sn | | (n-1)*O(l)，其中 l 是 max(len(s1),..,len(sn)) | | | 差集 s-t | O(len(s)) | | | | s.difference_update(t) | O(len(t)) | | | | 对称差集 s^t | O(len(s)) | O(len(s) * len(t)) | | | s.symmetric_difference_update(t) | O(len(t)) | O(len(t) * len(s)) | |
从 源代码 中可以看到，set 的差集操作 s-t 或 s.difference(t) 和就地差集操作 s.difference_update(t) 的复杂度是不一样的！
第一个操作是 O(len(s))（对于 s 中的每个元素，如果它不在 t 中，就将它添加到新的 set 中）。
第二个操作是 O(len(t))（对于 t 中的每个元素，从 s 中移除它）。
因此，必须小心选择哪个操作，这取决于哪个 set 更长，以及是否需要新的 set。
为了执行像 s-t 这样的 set 操作，s 和 t 都需要是 set。
然而，即使 t 是任何可迭代的对象，你也可以执行方法等效操作，例如 s.difference(l)，其中 l 是一个列表。
dict（字典）
为 dict 对象列出的平均情况时间复杂度，是基于假设对象的哈希函数足够强大，以使冲突不常出现。
平均情况假设在参数中使用的键是从所有键的集合中均匀随机选择的。
注意：对于只处理键为字符串的字典，确实有一个优化的路径。这就意味着，虽然时间复杂度在大 O 表示法中仍然是一样的，但是实际的执行速度可能会更快。
以下是字典各种操作的时间复杂度：
操作 | 平均时间复杂度 | 最坏时间复杂度 | | k in d | O(1) | O(n) | | 复制（注3） | O(n) | O(n) | | 获取元素 | O(1) | O(n) | | 设置元素（注1） | O(1) | O(n) | | 删除元素 | O(1) | O(n) | | 迭代（注3） | O(n) | O(n) |
备注
1. 这些操作依赖于 “摊销” 的 “摊销最坏情况” 部分。根据容器的历史操作和状态，单个操作可能会有意想不到的耗时（小甲鱼：例如，对于某些类型的数据结构，如果你频繁地添加和删除元素，那么数据结构可能会保持在一个 “扩展状态”，即使它的当前大小实际上已经变小了。这是因为数据结构根据预判，可能会预留空间以便将来添加更多元素……在这种情况下，搜索一个元素可能会比在一个从未扩展过的同样大小的数据结构上要慢）。
2. 从大小为 n 的列表中删除索引 k 处的元素会使用 memmove（C 语言函数）将 k 之后的所有元素向左移动一位。需要移动 n - k 个元素，因此该操作是 O(n - k)。最好的情况是删除倒数第二个元素，这需要移动一次，最坏的情况是删除第一个元素，这涉及到 n - 1 次移动。对于 k 的平均值，平均情况是删除列表中间的元素，这需要 O(n/2) = O(n) 次操作。
3. 对于这些操作，最坏的情况下的 n 是容器曾经达到的最大大小，而不仅仅是当前大小。例如，如果向字典中添加了 N 个对象，然后删除了 N-1 个对象，那么字典的大小仍将至少为 N 个对象，直到进行另一次插入操作。
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-8-29 03:44:29
置顶卡
千斤顶
显身卡
发表于 2023-8-29 10:33:32
发表于 2023-8-29 16:18:42
楼主