复杂度分析：主定理、摊还分析与均摊复杂度

复杂度分析是评估算法效率的理论工具，也是面试中经常被追问的环节。能清晰推导复杂度，是资深工程师的重要标志。

一、大 O 记号（Big-O Notation）

定义

f(n) = O(g(n))：存在正常数 c 和 n₀，使得 ∀n ≥ n₀，f(n) ≤ c·g(n)

常见复杂度排序

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

二、递归复杂度分析

代入法（Substitution Method）

T(n) = 2T(n/2) + O(n)
猜 T(n) = O(n log n)
验证：假设 T(k) ≤ ck log k 对 k < n 成立
T(n) ≤ 2·c(n/2)log(n/2) + an
     = cn(log n - 1) + an
     = cn log n - cn + an
     ≤ cn log n  （当 c ≥ a）

递归树法（Recursion Tree）

       cn                 ← 第 0 层：cn
      /   \
  cn/2     cn/2           ← 第 1 层：cn
   ...     ...
   c       c ... c        ← 第 log n 层：cn

共 log n + 1 层，每层和为 cn
总复杂度 = cn × (log n + 1) = O(n log n)

主定理（Master Theorem）

对于 T(n) = a·T(n/b) + f(n)：

情况 1：若 f(n) = O(n^(log_b(a) - ε))，则 T(n) = Θ(n^log_b(a))

情况 2：若 f(n) = Θ(n^log_b(a))，则 T(n) = Θ(n^log_b(a) · log n)

情况 3：若 f(n) = Ω(n^(log_b(a) + ε))，且 af(n/b) ≤ cf(n)，则 T(n) = Θ(f(n))

主定理应用示例

三、摊还分析（Amortized Analysis）

摊还分析计算操作的平均代价，但不依赖概率分布。

1. 聚合分析（Aggregate Analysis）

计算 n 个操作的总代价，除以 n。

动态数组扩容：

每次扩容两倍，假设初始容量 1
总插入代价 = n 次插入 + 扩容复制
           = n + (1 + 2 + 4 + ... + 2^k) 其中 2^k < n
           = n + (2n - 1)
           = 3n - 1
摊还代价 = O(3n)/n = O(1)

2. 记账方法（Accounting Method）

为每个操作预存「信用」，用于支付后续昂贵操作。

动态数组：

• 插入操作收费 3（实际代价 1 + 存储信用 2）
• 当扩容时，用存储的信用支付复制代价

3. 势能方法（Potential Method）

定义势函数 Φ，摊还代价 = 实际代价 + ΔΦ

Φ = 2 × (当前元素数 - 当前容量/2)

插入（无扩容）：实际 1，Φ 增加 2，摊还 = 3
插入（扩容）：实际 1 + 复制n个，Φ 从 2n 降到 0，摊还 = 3

4. 并查集（Union-Find）

带路径压缩的并查集，m 次操作摊还复杂度为 O(α(n))，其中 α 是阿克曼函数的反函数，增长极慢，实际可视为 O(1)。

四、空间复杂度分析

常见情况

空间优化技巧

• 滚动数组：将二维 DP 优化为一维
• 状态压缩：用位运算表示布尔状态
• 原地修改：在输入数组上操作，标记已访问

五、面试中常考的复杂度推导

1. 二分查找

每次问题规模减半：T(n) = T(n/2) + O(1)
主定理：a=1, b=2, f(n)=1, log_b(a)=0
情况 2：T(n) = O(log n)

2. 归并排序

T(n) = 2T(n/2) + O(n)
主定理情况 2：T(n) = O(n log n)

3. 快速排序（平均）

期望比较次数：E[C(n)] = n - 1 + (1/n) × Σ(E[C(k)] + E[C(n-k-1)])
解得：E[C(n)] = O(n log n)

4. 建堆

高度为 h 的节点最多 ⌈n/2^(h+1)⌉ 个
每个节点下沉 O(h)
总代价 = Σ(h=0 to log n) ⌈n/2^(h+1)⌉ × O(h)
       = O(n × Σ(h=0 to ∞) h/2^h)
       = O(n × 2) = O(n)

六、常见问题

Q: 时间复杂度和空间复杂度哪个更重要？

• 通常优先优化时间复杂度
• 空间换时间是常见策略（哈希表、缓存）
• 嵌入式/大数据场景可能优先空间

Q: 大 O、大 Ω、大 Θ 的区别？

• O：上界（最坏情况不超过）
• Ω：下界（最好情况至少）
• Θ：紧确界（既是上界也是下界）

Q: 为什么快排平均 O(n log n) 但最坏 O(n²)？

• 平均：每次较好划分，递归树平衡
• 最坏：每次最差划分（已有序），递归树退化为链

相关文章：

• 排序算法
• 动态规划