复杂度与 Python：先知道工具在做什么

选对容器通常比把一行代码写短更有用。先问：我要查找、计数、按顺序处理，还是不断取出最小值？

1. 复杂度不是数 for 的个数

for 里套 while，不一定是 O(n²)。如果两个指针都只往前走，每个最多移动 n 次，总共仍是 O(n)。反过来，一个 for 每次都做 values[:index]，复制长度从 0 到 n−1，累加就是 O(n²)。

这里默认整数运算、单次比较是 O(1)；遇到很大的 Python 整数、长字符串或 tuple key，要另算运算、比较或哈希的长度成本。

2. average 和 amortized 别混着说

• Average / expected：dict 查找通常 O(1)，依赖哈希分布等条件；极端碰撞可到 O(n)。
• Amortized：list.append 偶尔扩容很贵，但一长串追加摊下来，每次 O(1)。不是说每次追加都只花固定时间。

拿一个简化的动态数组来看：空间不够时，容量从 1 翻到 2，再翻到 4、8。每写入一个新元素算 1 次操作，扩容时每搬一个旧元素也算 1 次。

第 5 次明显更贵，但 8 次追加一共只做了 15 次操作。继续追加，搬运次数是 $1+2+4+\cdots$，加上新元素的写入，总成本仍是 O(n)。摊还分析（amortized analysis）不要求输入随机，也不是取多次测速的平均值。 这里的容量翻倍是教学模型，不是 CPython 的实际扩容序列。

def doubling_append_costs(count):
    capacity = 0
    costs = []
    for size in range(count):
        cost = 1
        if size == capacity:
            cost += size
            capacity = max(1, capacity * 2)
        costs.append(cost)
    return costs


assert doubling_append_costs(8) == [1, 2, 3, 1, 5, 1, 1, 1]
assert sum(doubling_append_costs(8)) == 15

哈希表（hash table）的“通常 O(1)”依赖的则是哈希分布等条件：如果大量 key 碰撞，查找就可能慢下来。表扩容也有摊还成本，但那是另一层分析，不能用来保证每次查找都快。

输入通常不计入辅助空间（auxiliary space）；新建的字典、递归栈（recursion stack）要算；返回全部答案的空间单独说，不要藏起来。

3. 容器速查

成本针对常见 Python 实现和上面的基本操作假设。接口见官方 dict / set、deque / Counter、heapq、bisect。

末尾 pop() 不用把后面的元素往前搬，但偶尔仍要收缩底层数组，所以这里也写“摊还”。可以对照 CPython 3.12 的 list_pop_impl 与 list_resize：常见的一步很便宜，不等于每一步都有固定耗时。

4. 几个常用函数

from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
import heapq

counts = Counter("banana")
groups = defaultdict(list)
groups["fruit"].append("pear")
queue = deque(["start"])
queue.append("next")
first = queue.popleft()
values = [1, 2, 2, 5]
left = bisect_left(values, 2)
right = bisect_right(values, 2)
heap = [5, 1, 3]
heapq.heapify(heap)
smallest = heapq.heappop(heap)

结果：counts['a'] == 3；first == 'start'；left == 1、right == 3，所以 2 出现了 right-left == 2 次；smallest == 1。

enumerate(values) 给下标和值；zip(first, second) 默认在短的那边结束；sorted(values, key=...) 返回新列表；values.sort() 原地改、返回 None。最大堆的负数法兼容较老 Python；Python 3.14 起也有公开的 heapify_max、heappush_max、heappop_max，先确认运行版本。

5. 递归、切片和输出都要算空间

一棵长成链的树：没有显式列表，递归（recursion）深度仍可达 n，调用栈（call stack）就是 O(n)。平衡二叉树才保证高度是 O(log n)。

values[left:right] 会复制这一段；''.join(parts) 也要创建输出字符串。原地修改不一定代表 O(1) 空间，例如排序内部还可能使用辅助缓冲。

6. 合上笔记，试一下

下一步：Hash map：到底要记住什么。