WARNING

🧪 Beta公测版本提示：教程主体已完成，正在优化细节，欢迎大家提Issue反馈问题或建议。

algo01 复杂度分析与渐进记号 — demo.py 代码详解

Download demo.py

运行方式

cd docs/algorithms/basics/complexity/code
python demo.py

代码逐段详解

第1步：导入库 — 每个库的作用

import os
import time
import math
import random
import matplotlib.pyplot as plt
import matplotlib

• os：文件路径操作，用于创建 images/ 目录和保存图片
• time：time.perf_counter() 提供高精度计时，用于测量算法运行时间
• math：math.log2() 计算以 2 为底的对数，用于理论复杂度曲线
• random：生成随机数组，用于排序算法的测试数据
• matplotlib：绘图库，用于可视化复杂度曲线、计时对比和均摊分析

第2步：五种复杂度等级的算法实现

本演示实现了五种不同复杂度等级的算法，对它们进行实际计时：

复杂度	算法	代码关键点
$O(1)$	数组索引	arr[n // 2] — 单次直接访问
$O(\log n)$	二分查找	while lo <= hi 循环每次将搜索空间减半
$O(n)$	线性求和	for x in arr: total += x — 遍历所有元素
$O(n\log n)$	归并排序	分治法：分解 $\log n$ 层，每层合并 $O(n)$
$O(n^2)$	冒泡排序	双重循环：外循环 $n$ 次，内循环 $n-i$ 次

二分查找的关键逻辑

初始: lo=0, hi=n-1, target=n-1 (最坏情况：目标在末尾)

第1步: mid = n/2,      arr[mid] < target → lo = mid+1  (一半排除)
第2步: mid = 3n/4,     arr[mid] < target → lo = mid+1  (又一半)
...
直到 lo > hi 时退出

每步排除一半候选，因此需要约 log₂(n) 步 → O(log n)

归并排序的 O(n log n) 来源

分解树:
               [n]
          /          \
      [n/2]          [n/2]
     /    \          /    \
  [n/4]  [n/4]    [n/4]  [n/4]
   ...    ...      ...    ...

每层合并总代价 = O(n)，总层数 = log₂(n)
总代价 = n × log₂(n) = O(n log n)

第3步：理论复杂度曲线可视化

plot_complexity_curves() 函数绘制两幅对比图：

1. 左图（线性坐标）：可以看到 $O(n^2)$ 和 $O(2^n)$ 迅速飙升，而 $O(\log n)$ 几乎贴在 x 轴上
2. 右图（双对数坐标）：使用 ax.loglog()，使得多项式函数 $O(n^k)$ 变成斜率为 $k$ 的直线，便于比较

为什么使用双对数坐标？ 因为 $\log (n^k)=k\log n$，所以在 log-log 图上 $O(n^k)$ 呈现为一条斜率为 $k$ 的直线。这让我们可以直观地"看出"复杂度等级。

第4步：实测计时对比

plot_benchmark_results() 对不同算法在多个输入规模下进行实际计时：

sizes = [100, 200, 500, 1000, 2000, 5000]

对于每个规模 n：
  1. 运行算法 3 次
  2. 取平均值（减小测量噪声）
  3. 记录运行时间

关键观察：

• $O(\log n)$ 的二分查找在 n=5000 时几乎测不出时间（微秒级）
• $O(n)$ 的线性求和时间随 n 线性增长
• $O(n^2)$ 的冒泡排序在 n=5000 时已经明显变慢（可能需要数秒）

第5步：动态数组均摊分析

这是本演示的核心内容。DynamicArray 类从零实现了一个类似 Python list 的动态数组：

class DynamicArray:
    def __init__(self):
        self._capacity = 1       # 初始容量为 1
        self._size = 0           # 当前元素个数
        self._data = [None] * 1  # 底层固定数组

append 操作的核心逻辑

append(value):
  1. 如果 size == capacity (数组已满):
     → 分配新数组，容量 = capacity × 2
     → 将旧数组所有元素复制到新数组（复制 size 次）
     → 更新 capacity
  2. 在 data[size] 处放入新值
  3. size += 1

扩容为何均摊 O(1)？

假设我们执行了 $n=16$ 次 append：

操作  容量  是否扩容  复制次数
  1    1    是(1→2)     0
  2    2    是(2→4)     1
  3    4    否           0
  4    4    是(4→8)     3
  5-7  8    否           0 (每次)
  8    8    是(8→16)    7
  9-15 16   否           0 (每次)
 16   16   是(16→32)   15
──────────────────────────
总复制次数 = 1 + 3 + 7 + 15 = 26
均摊复制 = 26/16 = 1.625

一般情况:
总复制次数 ≤ 2^{⌈log₂ n⌉} - 1 ≤ 2n - 1
均摊 = 总复制/n ≤ 2 = O(1)

直觉理解：随着 append 次数增多，扩容变得越来越"稀疏"。虽然有 $O(n)$ 的扩容操作，但它们被均摊到了 $n$ 次 $O(1)$ 操作中。

第6步：可视化均摊分析

demonstrate_amortized_analysis() 绘制两幅图：

1. 容量增长阶梯图：展示容量呈 2 的幂次阶梯式增长（1, 2, 4, 8, 16, 32...）
2. 均摊复制次数趋近曲线：展示累积复制次数/n 随着 n 增大趋近于常数（理论上限为 2）

---

关键概念速查表

概念	定义	数学表达	直观理解
大 O	渐进上界	$\mathrm{\exists }c,n_0:\mathrm{\forall }n\ge n_0,f(n)\le c\cdot g(n)$	"最坏也不会比这个差"
大 Ω	渐进下界	$\mathrm{\exists }c,n_0:\mathrm{\forall }n\ge n_0,f(n)\ge c\cdot g(n)$	"最好也不会比这个好"
大 Θ	渐进紧确界	既是 O 又是 Ω	"不多不少，就是这个"
均摊分析	序列操作的平均代价	$\frac{1}{n}\sum c_i$	"贵的操作摊到便宜的操作上"
势能法	用势能函数平滑代价	${\hat{c}}_i=c_i+\mathrm{\Delta }\mathrm{\Phi }$	"用银行里的存款付账"
主定理	分治递推式的通解	$T(n)=aT(n/b)+f(n)$	"三情形覆盖大多数分治算法"

---

源码位置

clone 后打开（相对仓库根目录）：

docs/algorithms/basics/complexity/code/demo.py