第 1 章

复杂度：衡量代码快慢的尺子

第一章：复杂度 — 衡量代码快慢的尺子

你写了两段代码来解决同一个问题，一段跑了 0.3 秒，另一段跑了 45 秒。你说第一段"更快"。但如果数据量从 1 万变成 1 亿呢？0.3 秒的那段可能变成 30 秒，而 45 秒的那段可能变成 45.001 秒。哪段更快？

这就是为什么我们需要复杂度分析。它不是在回答"这段代码跑多久"，而是在回答"当输入规模增长时，这段代码的运行时间如何增长"。

Level 1 · 你需要知道的

1.1 大 O 表示法的直觉

大 O 表示法描述的是增长趋势，不是精确时间。当我们说一个算法是 O(n) 的，意思是：当输入规模翻倍时，运行时间大约也翻倍。

最常见的复杂度，按从快到慢排列：

复杂度	名称	n=10	n=100	n=1000	n=10⁶	直觉
O(1)	常数	1	1	1	1	不管数据多大，时间不变
O(log n)	对数	3	7	10	20	每次排除一半
O(n)	线性	10	100	1000	10⁶	看一遍数据
O(n log n)	线性对数	33	664	9966	2×10⁷	好的排序算法
O(n²)	平方	100	10⁴	10⁶	10¹²	两层嵌套循环
O(2ⁿ)	指数	1024	10³⁰	—	—	穷举所有子集
O(n!)	阶乘	3.6×10⁶	—	—	—	穷举所有排列

关键直觉：O(n²) 和 O(n) 之间的差距，不是 2 倍，而是 n 倍。当 n = 10⁶ 时，这个差距是 100 万倍。

1.2 如何快速判断代码复杂度

规则一：看循环嵌套层数

# O(n) — 单层循环
for i in range(n):
    do_something()

# O(n²) — 两层嵌套
for i in range(n):
    for j in range(n):
        do_something()

# O(n³) — 三层嵌套
for i in range(n):
    for j in range(n):
        for k in range(n):
            do_something()

规则二：看循环变量的变化方式

# O(log n) — 每次翻倍或减半
i = 1
while i < n:
    i *= 2  # 翻倍

# O(sqrt(n)) — 循环到平方根
for i in range(int(n**0.5) + 1):
    do_something()

规则三：顺序执行取最大，嵌套执行取乘积

# O(n) + O(n²) = O(n²)  ← 取最大
for i in range(n):       # O(n)
    pass
for i in range(n):       # O(n²)
    for j in range(n):
        pass

# O(n) × O(m) = O(nm)  ← 取乘积
for i in range(n):       # 外层 n 次
    for j in range(m):   # 内层 m 次
        pass

规则四：递归看递归树

# O(2ⁿ) — 每次分两个子问题，规模减 1
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# O(n log n) — 每次分两个子问题，规模减半
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # T(n/2)
    right = merge_sort(arr[mid:])   # T(n/2)
    return merge(left, right)       # O(n)

1.3 空间复杂度

空间复杂度衡量的是算法额外使用的内存随输入规模的增长趋势。注意是"额外"的，不包括输入数据本身。

# 空间 O(1) — 只用了几个变量
def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

# 空间 O(n) — 创建了一个新数组
def double_array(arr):
    result = []
    for x in arr:
        result.append(x * 2)
    return result

# 空间 O(n) — 递归调用栈
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # 递归深度为 n

1.4 常见错误

错误 1：忽略隐藏的循环

# 看起来是 O(n)，实际是 O(n²)
for i in range(n):
    if i in some_list:  # list 的 in 是 O(n)！
        pass
# 修复：用 set
some_set = set(some_list)
for i in range(n):
    if i in some_set:   # set 的 in 是 O(1)
        pass

错误 2：字符串拼接陷阱

# O(n²)！每次 += 都创建新字符串
s = ""
for i in range(n):
    s += str(i)  # 复制整个字符串

# O(n)：用 join
s = "".join(str(i) for i in range(n))

错误 3：忽略排序的复杂度

# 看起来简单，但 sort 是 O(n log n)
arr.sort()
# 所以整体不可能低于 O(n log n)

错误 4：把 O(n) 说成 O(1)

# list.insert(0, x) 不是 O(1)，是 O(n)
# 因为要把所有元素往后移一位
arr.insert(0, 42)  # O(n)
arr.append(42)      # O(1) 均摊

1.5 Python 常见操作复杂度速查

操作	list	dict/set	说明
索引访问 `a[i]`	O(1)	O(1)
尾部追加 `append`	O(1) 均摊	—	偶尔扩容 O(n)
头部插入 `insert(0,x)`	O(n)	—	所有元素后移
删除 `del a[i]`	O(n)	O(1)	list 需要移动元素
查找 `x in a`	O(n)	O(1)	最常见的性能陷阱
排序 `sort()`	O(n log n)	—	TimSort
`len()`	O(1)	O(1)	预存长度
切片 `a[i:j]`	O(j-i)	—	复制元素

Level 2 · 它是怎么运行的

2.1 大 O 的数学定义

大 O 不是一个粗略的估计，而是一个严格的数学定义。

定义：如果存在正常数 c 和 n₀，使得对所有 n ≥ n₀ 都有 f(n) ≤ c·g(n)，则 f(n) = O(g(n))。

用人话说：当 n 足够大时，f(n) 的增长不会超过 g(n) 的常数倍。

举例：f(n) = 3n² + 7n + 42 是 O(n²) 的吗？

取 c = 4，n₀ = 10。当 n ≥ 10 时：

3n² + 7n + 42 ≤ 3n² + 7n² + 42n² = 52n² ≤ 4n²？
不对，让我重新算。3n² + 7n + 42 ≤ 3n² + n² + n² = 5n²（当 n ≥ 10 时，7n ≤ n², 42 ≤ n²）
取 c = 5, n₀ = 10，条件满足。所以 f(n) = O(n²)。

大 Ω（下界）：如果存在正常数 c 和 n₀，使得对所有 n ≥ n₀ 都有 f(n) ≥ c·g(n)，则 f(n) = Ω(g(n))。

大 Θ（精确界）：如果 f(n) = O(g(n)) 且 f(n) = Ω(g(n))，则 f(n) = Θ(g(n))。

换句话说，Θ 意味着增长速度恰好和 g(n) 相同（忽略常数倍）。

记号	含义	类比
f(n) = O(g(n))	f 增长不超过 g	f ≤ g（忽略常数）
f(n) = Ω(g(n))	f 增长不低于 g	f ≥ g（忽略常数）
f(n) = Θ(g(n))	f 增长与 g 相同	f = g（忽略常数）

面试中常见的误用：很多人说"这个算法的复杂度是 O(n)"，其实想表达的是 Θ(n)。O(n) 只是上界，一个 O(1) 的算法也是 O(n) 的（因为 O(1) ≤ O(n)），但说它是 Θ(n) 就错了。面试中这个区别通常不追究，但在论文和严格的算法分析中，这个区分很重要。

2.2 最好、最坏和平均情况

同一个算法对不同输入可能有不同的运行时间。

以线性搜索为例：在长度为 n 的数组中查找元素 x。

def linear_search(arr, x):
    for i, val in enumerate(arr):
        if val == x:
            return i
    return -1

最好情况 Best Case：x 在第一个位置 → O(1)
最坏情况 Worst Case：x 不在数组中 → O(n)
平均情况 Average Case：假设 x 等概率出现在任意位置 → O(n/2) = O(n)

惯例：当我们说"复杂度是 O(n)"而不加限定时，通常指的是最坏情况。这是一种保守但安全的估计。

快速排序是一个特殊的例子：

最坏情况：O(n²)（每次选到最大或最小的元素作为 pivot）
平均情况：O(n log n)（随机选 pivot 时）
实践中我们通常说快排是 O(n log n) 的，因为平均情况在实践中更有代表性

2.3 均摊分析（Amortized Analysis）

有些操作大部分时候很快，偶尔很慢。均摊分析的思想是：把偶尔的高成本分摊到大量的低成本操作上。

经典案例：Python list.append()

Python 的 list 内部是一个动态数组。当数组满了，append 需要：

分配一个更大的新数组（通常是当前容量的 ~1.125 倍）
把所有元素复制到新数组
释放旧数组

复制操作是 O(n) 的。但这种扩容不是每次 append 都发生，大部分 append 只需要 O(1)。

import sys

sizes = []
old_size = 0
lst = []
for i in range(100):
    lst.append(i)
    new_size = sys.getsizeof(lst)
    if new_size != old_size:
        sizes.append((i, new_size))
        old_size = new_size

# 输出部分结果：
# (0, 88)   → 初始分配
# (4, 120)  → 容量 4→8
# (8, 184)  → 容量 8→16
# (16, 248) → 容量 16→25
# 扩容不是每次都发生

假设我们执行 n 次 append，总共需要复制多少次元素？

扩容发生在容量为 1, 2, 4, 8, 16, ..., n 的时候（假设每次翻倍），每次扩容复制的元素数分别是 1, 2, 4, 8, ..., n。

总复制次数 = 1 + 2 + 4 + 8 + ... + n = 2n - 1 ≈ 2n

所以 n 次 append 的总成本是 O(n)，每次 append 的均摊成本是 O(n) / n = O(1)。

直觉理解：你存钱存了 99 天，每天 1 块；第 100 天要交 100 块的房租。平均下来每天花 2 块。均摊分析就是这个意思。

2.4 主定理（Master Theorem）

很多分治算法的递推关系可以用主定理快速得出复杂度。

定理：如果 T(n) = aT(n/b) + O(nᵈ)，其中 a ≥ 1, b > 1, d ≥ 0，则：

条件	结果
d > log_b(a)	T(n) = O(nᵈ)
d = log_b(a)	T(n) = O(nᵈ log n)
d < log_b(a)	T(n) = O(n^(log_b(a)))

应用示例：

归并排序：T(n) = 2T(n/2) + O(n)
  a=2, b=2, d=1 → log₂2 = 1 = d → O(n log n) ✓

二分查找：T(n) = T(n/2) + O(1)
  a=1, b=2, d=0 → log₂1 = 0 = d → O(log n) ✓

Karatsuba 乘法：T(n) = 3T(n/2) + O(n)
  a=3, b=2, d=1 → log₂3 ≈ 1.585 > d → O(n^1.585) ✓

Strassen 矩阵乘法：T(n) = 7T(n/2) + O(n²)
  a=7, b=2, d=2 → log₂7 ≈ 2.807 > d → O(n^2.807) ✓

记忆方法：比较 d 和 log_b(a) 的大小。d 大说明"合并的工作主导"（结果是 nᵈ）；log_b(a) 大说明"递归的子问题数量主导"（结果是 n^(log_b(a))）；相等就多乘一个 log。

2.5 递归树分析

主定理只适用于特定形式的递推。对于不规则的递归，我们需要画递归树。

以斐波那契递归为例：

                    fib(5)
                   /      \
              fib(4)        fib(3)
             /     \        /    \
         fib(3)   fib(2)  fib(2) fib(1)
         /   \     / \     / \
     fib(2) fib(1) ...   ...
      / \
  fib(1) fib(0)

每一层的节点数大约是上一层的 2 倍（不精确，因为左子树比右子树深一层），总共约有 2⁰ + 2¹ + ... + 2ⁿ ≈ 2ⁿ 个节点。

所以朴素递归斐波那契的复杂度是 O(2ⁿ)。更精确地说是 O(φⁿ)，其中 φ = (1 + √5) / 2 ≈ 1.618 是黄金分割比（因为递归树不是完美二叉树）。

对比：用动态规划（自底向上循环）计算斐波那契只需要 O(n)：

def fib_dp(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

从 O(1.618ⁿ) 到 O(n)，这就是算法设计的力量。当 n = 50 时，朴素递归需要约 10¹⁰ 次操作（几十秒），DP 只需要 48 次加法（微秒级）。

Level 3 · 规范怎么定义的

3.1 Bachmann-Landau 记号的历史

大 O 记号并非计算机科学的发明。

1894 年，德国数学家 Paul Bachmann 在其著作 Die Analytische Zahlentheorie（解析数论）中首次使用 O 记号来描述函数增长的上界。他写的是 O(n)，意思是"阶不超过 n 的量"。

1909 年，Edmund Landau 在他的教科书中系统化了这套记号，并引入了小 o 记号（严格上界）。因此这套符号系统被称为 Bachmann-Landau 记号。

1976 年，Donald Knuth 在论文 Big Omicron and Big Omega and Big Theta（发表于 SIGACT News）中提出了 Θ 记号，并论证了为什么需要区分上界（O）、下界（Ω）和精确界（Θ）。他写道：

"Many people have been using O-notation in a sloppy way... it is important to have a notation for exact order of growth."

"很多人在草率地使用 O 记号... 有一个表示精确增长阶的记号是很重要的。"

Knuth 的这篇论文奠定了我们今天使用的三件套：O、Ω、Θ。

3.2 均摊分析的三种方法

均摊分析由 Robert Tarjan 在 1985 年的论文 Amortized Computational Complexity 中系统化（发表于 SIAM Journal on Algebraic and Discrete Methods）。他提出了三种等价的分析方法：

方法一：聚合法（Aggregate Method）

计算 n 次操作的总成本 T(n)，然后均摊成本 = T(n) / n。

以动态数组扩容为例：

假设初始容量为 1，每次满时容量翻倍
n 次 append 中，扩容发生在第 1, 2, 4, 8, ..., 2^k 次（其中 2^k ≤ n）
每次扩容复制 i 个元素
总复制次数 = 1 + 2 + 4 + ... + 2^k ≤ 2n
加上 n 次普通写入，总成本 T(n) ≤ 3n
均摊成本 = 3n / n = O(1)

方法二：记账法（Accounting Method）

给每个操作预先"收费"。如果某次操作的实际成本低于收费，多出的部分存为"信用"；如果实际成本高于收费，用之前积累的信用支付。只要信用永远不为负，收费就是有效的均摊成本。

动态数组的记账法：

每次 append 收 3 个 coin（而不是实际的 1 个）
1 个 coin 支付本次写入
2 个 coin 存起来作为未来扩容的"搬家基金"
当扩容发生时，需要复制 n/2 个"老元素"到新数组（另一半 n/2 是刚加入的，已经在正确位置）
这 n/2 个老元素每个都有 2 个 coin 的积蓄，总共 n 个 coin，刚好够支付复制
信用永远 ≥ 0，所以均摊成本 O(3) = O(1)

方法三：势能法（Potential Method）

定义一个"势能函数" Φ，将数据结构的状态映射到一个非负实数。均摊成本 = 实际成本 + ΔΦ（势能变化）。

动态数组的势能法：

定义 Φ(D) = 2 × size - capacity（size 是当前元素数，capacity 是数组容量）
普通 append：实际成本 = 1，Φ 增加 2（size 增 1），均摊 = 1 + 2 = 3
扩容 append：实际成本 = 1 + old_cap（复制），Φ 从 2×old_cap - old_cap = old_cap 变为 2×(old_cap+1) - 2×old_cap = 2 - old_cap
ΔΦ = (2 - old_cap) - old_cap = 2 - 2×old_cap
均摊 = (1 + old_cap) + (2 - 2×old_cap) = 3 - old_cap ≤ 3

三种方法得到相同的结论：动态数组 append 的均摊复杂度是 O(1)。

3.3 哈希表均摊分析的陷阱

Python 的 dict 在负载因子超过 2/3 时触发 rehash，将所有键值对重新分配到更大的表中。这和动态数组类似，rehash 是 O(n) 的，但均摊下来每次插入仍然是 O(1)。

但有一个陷阱：哈希冲突在最坏情况下不是 O(1)。

如果所有键都映射到同一个桶（比如精心构造的恶意输入），查找退化为链表遍历 O(n)。Python 3.6+ 使用的 CPython 实现用了开放寻址 + 扰动函数来减轻这个问题，但理论上最坏情况仍然是 O(n)。

Java 的 HashMap 在 Java 8+ 对此做了一个有趣的优化：当单个桶中的链表长度超过 8 时，自动转换为红黑树，使最坏情况从 O(n) 变为 O(log n)。这是一个工程妥协——大部分情况下链表更快（节省了树节点的额外空间和旋转开销），只在极端情况下才"升级"到树。

3.4 小 o 与小 ω

除了大 O/Ω/Θ，还有两个不太常用但在理论分析中重要的记号：

小 o：f(n) = o(g(n)) 表示 f(n) 严格增长慢于 g(n)。即 lim(n→∞) f(n)/g(n) = 0。
- 例：n = o(n²)，但 n ≠ o(n)。
小 ω：f(n) = ω(g(n)) 表示 f(n) 严格增长快于 g(n)。即 lim(n→∞) f(n)/g(n) = ∞。

记号	类比不等式
O	≤
o	<
Ω	≥
ω	>
Θ	=

这五个记号构成了 Bachmann-Landau 记号的完整体系。

Level 4 · 边界与陷阱

4.1 为什么 O(n) 有时候比 O(log n) 快

大 O 丢弃了常数因子。当常数因子差异足够大时，"更优"的复杂度反而更慢。

案例：二分查找 vs 线性查找（小数组）

import time

# 二分查找 O(log n)
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# 线性查找 O(n)
def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

# 在长度为 10 的数组上，线性查找通常更快
arr = list(range(10))
# 因为线性查找的循环更简单，分支预测更友好
# 而二分查找有更多的比较、计算 mid、条件跳转

在 n < 64 的场景下，线性查找经常快于二分查找。这就是为什么很多排序算法（如 TimSort、introsort）在子数组足够小时会切换到插入排序（O(n²)），因为对小数组来说，O(n²) 的常数因子远小于 O(n log n) 的。

案例：Cache 局部性

# 遍历二维数组
n = 10000
matrix = [[0] * n for _ in range(n)]

# 按行遍历（Cache 友好）— 快
for i in range(n):
    for j in range(n):
        matrix[i][j] = 1

# 按列遍历（Cache 不友好）— 慢 5-10 倍
for j in range(n):
    for i in range(n):
        matrix[i][j] = 1

两段代码的复杂度都是 O(n²)，但按行遍历可能快 5-10 倍。因为 CPU Cache 是以缓存行（Cache Line，通常 64 字节）为单位加载的。按行遍历时，访问连续内存，一次 Cache Line 加载就能满足多次访问；按列遍历时，每次访问都跳到不同的 Cache Line，几乎每次都 Cache Miss。

这就是为什么复杂度分析不是全部。它告诉你增长趋势，但不告诉你常数因子和 Cache 行为。实际优化中，这两个因素经常比 O 分析更重要。

4.2 Python 中的隐藏复杂度

Python 的很多操作看起来很"轻"，但实际复杂度可能出人意料。

操作	你以为	实际	原因
`x in list`	O(1)	O(n)	线性扫描
`list.insert(0, x)`	O(1)	O(n)	所有元素右移
`list.pop(0)`	O(1)	O(n)	所有元素左移
`list + list`	O(1)	O(n+m)	创建新列表并复制
`list * k`	O(1)	O(nk)	复制 k 份
`str += str`	O(1)	O(n)	创建新字符串
`min(list)` / `max(list)`	O(1)	O(n)	线性扫描
`list.count(x)`	O(1)	O(n)	线性扫描
`list.index(x)`	O(1)	O(n)	线性扫描
`sorted(list)`	O(n)	O(n log n)	TimSort

最危险的是在循环内部使用这些 O(n) 操作，造成 O(n²)：

# 悲剧：O(n²)
result = []
for item in items:
    if item not in result:  # O(n) 查找
        result.append(item)

# 正确：O(n)
seen = set()
result = []
for item in items:
    if item not in seen:    # O(1) 查找
        seen.add(item)
        result.append(item)

4.3 递归的栈空间陷阱

递归的空间复杂度容易被忽略。每次递归调用都会在调用栈上分配一个栈帧（存储局部变量、返回地址等）。

# 空间 O(n) — 递归深度为 n
def sum_recursive(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)

# 空间 O(1) — 循环实现
def sum_iterative(arr):
    total = 0
    for x in arr:
        total += x
    return total

Python 默认递归深度限制是 1000（sys.getrecursionlimit()）。超过这个深度会抛出 RecursionError。对于可能达到大规模输入的算法，优先使用循环而不是递归。

但有些算法天然是递归的（如树遍历、分治）。此时递归深度通常是 O(log n)（平衡树的高度），不会触及限制。只有在链式结构（如单链表遍历用递归、不平衡的二叉树）中递归深度才会达到 O(n)。

4.4 面试经典：时间 vs 空间权衡

很多问题可以通过空间换时间来优化：

# 两数之和 — 暴力：O(n²) 时间，O(1) 空间
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# 两数之和 — 哈希表：O(n) 时间，O(n) 空间
def two_sum_hash(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

面试中如何回答：先给出暴力解并分析复杂度，然后说"我们可以用哈希表做到 O(n) 时间、O(n) 空间的 trade-off"，展示你理解权衡。

4.5 算法竞赛中的经验法则

竞赛中通常需要在 1-2 秒内完成。以下是根据时间限制估算可接受复杂度的经验法则：

n 的范围	可接受的复杂度	典型算法
n ≤ 20	O(2ⁿ) 或 O(n!)	暴力搜索、状态压缩 DP
n ≤ 500	O(n³)	Floyd、区间 DP
n ≤ 5000	O(n²)	简单 DP、暴力枚举
n ≤ 10⁶	O(n log n)	排序、二分、线段树
n ≤ 10⁸	O(n)	双指针、前缀和、线性 DP
n ≤ 10¹⁸	O(log n) 或 O(√n)	二分、快速幂、数论

这个表格价值很高：看到 n ≤ 10⁶，立刻知道需要 O(n log n) 或更优的算法。这能帮你在面试中快速排除不可行的思路。

4.6 复杂度不是唯一的衡量标准

在实际工程中，以下因素可能比 O 分析更重要：

Cache 命中率：连续内存访问（数组）比随机内存访问（链表、树）快得多
分支预测：简单的循环比复杂的条件判断更 CPU 友好
内存分配：频繁 malloc/free 的开销可能超过计算本身
并行度：O(n) 的串行算法可能慢于 O(n log n) 的可并行算法
I/O 瓶颈：当数据在磁盘上时，减少随机读写比减少计算更重要（这就是 B+Tree 存在的原因）

我们将在后续章节中反复看到这些因素。特别是第 2 章（数组与 Cache 友好性）、第 20 章（B+Tree 与磁盘 I/O）和第 40 章（数据结构选型指南）会深入讨论。

本章小结

概念	要点
大 O	增长上界，丢弃常数和低阶项
大 Ω	增长下界
大 Θ	精确增长阶
均摊分析	偶尔的高成本分摊到大量低成本操作上
主定理	T(n) = aT(n/b) + O(nᵈ) 的快速求解
常数因子	O 丢弃的常数在实践中可能决定胜负
Cache 效应	内存访问模式比算法复杂度更影响性能

练习题：

分析以下代码的时间和空间复杂度：

def mystery(n):
    if n <= 0:
        return 1
    return mystery(n - 1) + mystery(n - 1)

Python 中 collections.deque 的 appendleft 是 O(1) 还是 O(n)？为什么 list 的 insert(0, x) 是 O(n) 而 deque 可以做到 O(1)？
给定 n = 10⁷，以下哪些算法在 1 秒内能跑完（假设每秒 10⁸ 次操作）？
- O(n) → 10⁷ 次 → ✓
- O(n log n) → ~2.3 × 10⁸ 次 → 勉强
- O(n√n) → ~3.16 × 10¹⁰ 次 → ✗
- O(n²) → 10¹⁴ 次 → ✗

下一章预告：第 2 章将深入数组——连续内存如何让简单的遍历比链表快 10 倍，Python list 内部的扩容策略源码，以及为什么"Cache 友好"是高性能代码的第一准则。

本章评分

4.7 / 5 (123 评分)