Python 内置类型操作时间复杂度详解
Time complexity of operations on Python's built-in types
深入解析 CPython 中各类内置类型（如 list、dict、set、str 等）操作的时间复杂度。文档详细列出了从列表的插入删除到字典的哈希查找，再到集合运算的具体性能表现，并特别指出了最坏情况下的性能退化风险。了解这些底层机制，能帮助开发者在编写高性能 Python 代码时做出更明智的数据结构选择，避免在关键路径上踩坑。
列表的最大开销来自于超出当前分配大小的增长（因为所有元素都必须移动），或者在开头附近进行插入或删除（因为后续所有元素都必须移动）。
HN 评论区
42- alexpotato
Dave Beazley 有一场非常精彩的演讲，讲的是如何利用 Python 内置函数 [0] 进行数据分析和其他快速操作。
顺便提一句，虽然这些年我用过很多这些内置函数，但受 LLM 影响，现在用得越来越少。重看这个视频，感觉就像在看野外生存专家只用一把刀和一把锯子做椅子……
- Retr0id
太棒了。之前这些内容只在 wiki 上以半非官方的形式记录过：https://wiki.python.org/moin/TimeComplexity
- StellarScience
Python 众所周知是围绕哈希表构建的。甚至在前几个版本中，他们对哈希表实现进行了一次改进，结果整个语言的速度提升了百分之几。
不过，令我惊讶的是，这里完全没有提到任何时间复杂度为 O(log(N)) 的数据结构。难道真的没有需要这种复杂度的使用场景吗？
- mwkaufma
O(n - k) 或 O(len(l1) + len(l2)) 不就是 O(n) 吗？与其模糊复杂度分析和周期计数之间的界限，不如将复杂度和估算的相对周期数作为两个独立的指标分别列出。
- wodenokoto
为什么 `min(r)` 和 `max(r)` 对于 range 对象的时间复杂度是 O(n)？
我以为 min 和 max 是对象中存储的常量。本质上你只是在请求它创建时传入的参数之一。