算法复杂度分析大O表示法与主定理

可视化演示

通过增长速率对比、主定理递归树和均摊分析三个模式，展示大O表示法的渐进分析与复杂度求解方法。

渐进分析三记号

厨房里，大家讨论一道菜的时间往往用三种说法：有人问“最久要多久”，你会说“最多不超过两小时”，这是上界；有人问“再快能多快”，你会说“起码半小时”，这是下界；还有人想知道“通常稳定在多少”，你会说“大约四十五分钟，上下浮动十分钟”，这是紧密界。渐进分析就是把“数据规模 n 越来越大”这个条件代入，看运行时间函数被什么样的标准曲线框住。

在数学上，我们用函数集合来描述这种直觉。设 \(f(n)\) 是算法实际运行时间，\(g(n)\) 是我们拿来比较的标准函数：

\[

\begin{aligned}

O(g(n)) &= \{ f(n): \exists c>0, n_0>0,\ 0\le f(n)\le c\,g(n),\ \forall n\ge n_0 \},\\

\Omega(g(n)) &= \{ f(n): \exists c>0, n_0>0,\ 0\le c\,g(n)\le f(n),\ \forall n\ge n_0 \},\\

\Theta(g(n)) &= \{ f(n): \exists c_1,c_2>0,\ n_0>0,\ c_1 g(n)\le f(n)\le c_2 g(n),\ \forall n\ge n_0 \}.

\end{aligned}

\]

1. O 上界条件：存在一个常数 \(c\)，让 \(g(n)\) 放大若干倍后，从某个规模 \(n_0\) 开始一直压住 \(f(n)\)。

$$0\le f(n)\le c\,g(n), \quad \forall n\ge n_0$$

2. Ω 下界条件：反过来，放大后的 \(g(n)\) 能被 \(f(n)\) 压住，说明算法至少需要这个量级。

$$0\le c\,g(n)\le f(n), \quad \forall n\ge n_0$$

3. Θ 夹逼条件：同一次比较中，上下各一个常数倍数，把 \(f(n)\) 死死夹在 \(g(n)\) 附近。

$$c_1 g(n)\le f(n)\le c_2 g(n)$$

4. n₀ 的含义：我们只关心“足够大的数据量”，小规模的偶然抖动不算数。

$$n\ge n_0 \Rightarrow \text{进入稳定增长区}$$

厨师不会因为某桌客人只点一碗白饭就重估整本菜谱，他们关心的是晚市高峰期的大批量订单；渐进分析同理，关注大 n 下的趋势，而非小样本的偶然表现。

大O表示法

主厨做周末宴席时，会假设最忙的晚上八点：每桌都点招牌菜、每个灶台都在烧、每口锅都在炒。大 O 表示法也是这样，习惯性地看“最坏情况”。它回答的问题是：当输入规模 n 大到失控时，时间最多涨成什么样？

举例来说，某个算法的运行时间是 \(f(n)=3n^2+2n+1\)。我们想证明它属于 \(O(n^2)\)，只需要找到一个常数 \(c\) 和一个起始点 \(n_0\)，让放大后的 \(n^2\) 能压住所有项：

\[

3n^2+2n+1 \le 3n^2+2n^2+n^2 = 6n^2, \quad n\ge 1

\]

1. 放大每一项：把 \(2n\) 和 \(1\) 分别放大成 \(2n^2\) 和 \(n^2\)，让它们都能被 \(n^2\) 统一衡量。

$$3n^2+2n+1 \le 3n^2+2n^2+n^2$$

2. 合并同类项：右边合并成 \(6n^2\)，于是找到常数 \(c=6\)。

$$3n^2+2n^2+n^2 = 6n^2$$

3. 找到 n₀：因为放大操作依赖 \(n\ge 1\)，所以取 \(n_0=1\)。

$$\forall n\ge 1,\ 3n^2+2n+1 \le 6n^2$$

4. 下结论：这就是 \(f(n)=O(n^2)\)，说明当 n 增大时，时间会被一个二次函数“兜住”。

$$f(n)=O(n^2)$$

这里的 \(c\)、\(n_0\) 就像“可以多开两个备菜窗口”的余量。真实运行中常数可能很大，但只要增长趋势是二次的，数据量翻倍时耗时大约会变四倍——这才是大 O 想传达的警告。

递归方程求解

有些菜谱需要反复套娃：炖一锅高汤，先把食材对半切开，分别小火炖，最后再把两锅混合调味。每次切割是 \(O(1)\)，合并是 \(O(n)\)，子汤的规模变成原来一半。这种“自己调用自己”的时间开销，写成递归方程就是 \(T(n)=2T(n/2)+n\)。

迭代展开法非常直观：把 \(T(n/2)\) 再拆开，一层层往外拉，直到拆到边界条件 \(T(1)=1\)。

\[

T(n)=2T\left(\frac n2\right)+n

=2\left(2T\left(\frac n4\right)+\frac n2\right)+n

=4T\left(\frac n4\right)+2n

\]

继续展开 \(k\) 层后，子问题规模变成 \(n/2^k\)，每一层的额外成本都是 \(n\)，所以：

\[

T(n)=2^kT\left(\frac{n}{2^k}\right)+kn \xrightarrow{k=\log_2 n} n\log_2 n + n = \Theta(n\log n)

\]

1. 展开第一层：代入 \(T(n/2)\)，拆成两个子问题加一次合并成本。

$$T(n)=2T(n/2)+n=2\left(2T(n/4)+n/2\right)+n$$

2. 观察层数成本：每展开一层，子问题数量翻倍，但每个子问题规模减半，每层合并成本总和仍是 \(n\)。

$$4T(n/4)+2n = 8T(n/8)+3n$$

3. 推广到 k 层：写通式，\(2^k\) 个子问题，每个规模 \(n/2^k\)，累计了 \(k\) 个 \(n\)。

$$T(n)=2^kT(n/2^k)+kn$$

4. 代入终止条件：当 \(n/2^k=1\) 时 \(k=\log_2 n\)，此时子问题数为 \(n\)，边界总成本为 \(n\)。

$$T(n)=nT(1)+n\log_2 n = n + n\log_2 n$$

5. 决定量级：\(\log_2 n\) 项增长快于常数项，所以最终是 \(\Theta(n\log n)\)。

$$n\log_2 n + n = \Theta(n\log n)$$

递归树方法就是把上面的展开过程画成一棵树，每层节点数量乘以每个节点的成本求和。很多分治算法，比如归并排序、快速排序的期望情况，最后都会落到这张“分层成本表”上。

主定理全解

老师傅看递归方程，不需要每次一层层展开，而是直接用一套“行情表”快速估价。主定理就是这张表，它针对形如 \(T(n)=aT(n/b)+f(n)\) 的递归式：把规模为 n 的问题拆成 a 个子问题，每个规模为 \(n/b\)，再花 \(f(n)\) 做合并/拆解。关键看“子问题的总工作量 \(n^{\log_b a}\)”和“合并成本 \(f(n)\)”谁在增长中占主导：

\[

T(n)=

\begin{cases}

\Theta(n^{\log_b a}), & f(n)=O(n^{\log_b a-\varepsilon}),\ \varepsilon>0\\

\Theta(n^{\log_b a}\log n), & f(n)=\Theta(n^{\log_b a})\\

\Theta(f(n)), & f(n)=\Omega(n^{\log_b a+\varepsilon}),\ \varepsilon>0\text{ 且 } af(n/b)\le cf(n)

\end{cases}

\]

1. 标准形式：\(a\) 是子问题个数，\(b\) 是规模缩小的倍数，\(f(n)\) 是拆分和合并成本。

$$T(n)=aT(n/b)+f(n),\quad a\ge1,\ b>1$$

2. 计算关键指数：\(\log_b a\) 决定“子问题总数带来的总叶子成本”增长得有多快。

$$n^{\log_b a}$$

3. 情况一：叶子主导：如果 \(f(n)\) 多项式地小于这个指数，总成本由最底层的大量叶子决定。

$$f(n)=O(n^{\log_b a-\varepsilon}) \Rightarrow T(n)=\Theta(n^{\log_b a})$$

4. 情况二：两边均衡：如果 \(f(n)\) 正好落在同阶，每一层成本相当，总成本要再乘一个 \(\log n\)。

$$f(n)=\Theta(n^{\log_b a}) \Rightarrow T(n)=\Theta(n^{\log_b a}\log n)$$

5. 情况三：合并主导：如果 \(f(n)\) 多项式地大于指数，总成本由顶层的合并过程决定。

$$f(n)=\Omega(n^{\log_b a+\varepsilon}) \Rightarrow T(n)=\Theta(f(n))$$

例如归并排序 \(T(n)=2T(n/2)+n\)，\(a=2,b=2\)，\(\log_2 2=1\)，而 \(f(n)=n=\Theta(n^1)\)，落入情况二，所以是 \(\Theta(n\log n)\)。主定理让“递归复杂度估时”从手工展开变成了查表。

主定理条件

再好的行情表也有使用前提，就像“例汤炖两小时”的规律，只适用于稳定火力和固定食材。主定理要成立，必须满足几个约束：\(a\ge1\) 是至少有一个子问题，\(b>1\) 是每个子问题规模必须严格缩小。更重要的是，\(f(n)\) 与 \(n^{\log_b a}\) 之间必须存在“多项式差距”，而不是仅仅差一个对数因子。

正则条件进一步要求合并成本不能“越合并越离谱”：

\[

a f\left(\frac nb\right) \le c f(n), \quad c<1, \ \text{对足够大的 } n

\]

1. 参数约束：\(a\) 必须是不小于 1 的常数，\(b\) 必须大于 1，否则问题规模根本不缩小。

$$a\ge1,\quad b>1$$

2. 多项式差：情况一和情况三要求 \(f(n)\) 与 \(n^{\log_b a}\) 相差一个 \(n^\varepsilon\) 的“数量级鸿沟”。

$$\text{差距}=n^{\log_b a\pm\varepsilon},\quad \varepsilon>0$$

3. 正则条件：约束合并成本不会在递归中累积失控，这是情况三额外需要的条件。

$$a f(n/b)\le c f(n),\quad c<1$$

4. 不适用情形：如果 \(f(n)\) 是 \(n^{\log_b a}\log n\) 这类“差一点”的函数，或递归式不是标准分割形式（如 \(T(n)=T(n-1)+n\)），主定理就不能直接用。

一旦主定理不适用，就要退回迭代展开、递归树或代入法。这就像遇到非标准菜谱时，老师傅也只能老老实实重新称料。

均摊分析

宴席上有一道佛跳墙要炖三天，其他菜只要十分钟。如果只盯着一道菜，会觉得厨师根本忙不过来；但把整场宴席几十道菜放在一起算，三天一锅汤可被无数个十分钟匀开。均摊分析就是这个思路：不关心单次操作是否昂贵，只关心连续执行 \(n\) 次操作的总成本，再平均到每次。

最经典的例子是动态数组（比如 Python 的 list 追加元素）。平时一次插入就是写一个格子，成本是 1；但当数组装满时，需要申请一块更大的空间，把旧元素全部复制过去，这个瞬间的成本是 \(O(n)\)。

\[

\sum_{i=1}^{n} c_i \le n + \sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j < n + 2n = 3n

\]

1. 普通插入成本：数组没满时，一次追加写一个元素，成本为 1。

$$c_i = 1$$

2. 扩容复制成本：第 \(j\) 次扩容需要复制 \(2^j\) 个旧元素，成本为 \(2^j\)。

$$c_i = 2^j\quad(\text{扩容那一刻})$$

3. 累加所有扩容：从 1 开始不断翻倍，所有复制成本之和小于 \(2n\)。

$$\sum_{j=0}^{\log_2 n} 2^j = 2^{\log_2 n+1}-1 < 2n$$

4. 总成本上界：\(n\) 次普通插入加上复制成本，整体不超过 \(3n\)。

$$\sum_{i=1}^{n} c_i < 3n$$

5. 均摊结论：总成本除以次数 \(n\)，本质是有常数上界的。

$$\frac{1}{n}\sum_{i=1}^{n} c_i = O(1)$$

均摊分析不是“平均情况分析”，它不依赖输入的概率分布；它保证的是：对于任何连续 \(n\) 次操作，总成本都不会超过某个渐进上界。这就是佛跳墙账本的严谨版。

势能法

均摊分析像事后算总账，而势能法像提前办一张“时间银行卡”：每次操作如果很便宜，就多存一些“时间币”进账户；如果遇到昂贵操作，就从账户里取币覆盖额外开销。这个账户余额就被称为势能函数 \(\Phi(D_i)\)。

设 \(D_i\) 是第 \(i\) 次操作后的数据结构状态，\(\Phi(D_i)\) 是当前账户余额。第 \(i\) 次操作的实际成本是 \(c_i\)，但记账时我们记“摊还成本”：

\[

\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})

\]

1. 定义势能差：势能差 \(\Phi(D_i)-\Phi(D_{i-1})\) 模拟“这次是存钱还是取钱”。

$$\Delta\Phi = \Phi(D_i) - \Phi(D_{i-1})$$

2. 摊还成本公式：把实际开销和势能变化加在一起，就是这次操作记在账本上的成本。

$$\hat{c}_i = c_i + \Delta\Phi$$

3. 总成本关系：把所有操作加起来，势能变化会相互抵消，只剩下头尾两项。

$$\sum_{i=1}^{n}\hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n)-\Phi(D_0)$$

4. 可覆盖条件：只要最终势能不小于初始势能，摊还总和就大于等于实际总和，说明没有“虚记”。

$$\Phi(D_n)\ge \Phi(D_0) \Rightarrow \sum \hat c_i \ge \sum c_i$$

回到动态数组：设势能函数 \(\Phi=2\times size-capacity\)，每次普通插入存入 2 个单位，扩容时用存款支付复制成本，最终每次操作的摊还成本都是常数。势能法比聚合分析更灵活，因为它可以按“状态”而非“次数”来做账。

复杂度增长与工程

菜单从 10 人变成 1000 人时，不同做法的差距会被迅速放大：O(1) 的“取一碗饭”始终是一勺；O(log n) 的“查楼层号”只是多按几次电梯；O(n) 的“逐桌点单”人数翻十倍时间翻十倍；O(n²) 的“同桌两两碰杯”则让人直接崩溃。建立增长阶梯，才能在选算法时不靠感觉：

\[

O(1) \prec O(\log n) \prec O(n) \prec O(n\log n) \prec O(n^2) \prec O(2^n)

\]

为了感受差距，可以看 \(n\) 取 1000 时，\(n^2\) 比 \(n\log_2 n\) 大多少倍：

\[

\lim_{n\to\infty}\frac{n^2}{n\log_2 n} = \lim_{n\to\infty}\frac{n}{\log_2 n} = \infty

\]

1. 复杂度阶梯：按照增长快慢，把常见复杂度从低到高排成一个链条。

$$O(1) \prec O(\log n) \prec O(n) \prec O(n\log n) \prec O(n^2) \prec O(2^n)$$

2. 写出比值：取 \(O(n^2)\) 和 \(O(n\log n)\) 做比值，看谁增长更快。

$$\frac{n^2}{n\log_2 n} = \frac{n}{\log_2 n}$$

3. 取极限：分子线性增长，分母对数增长，比值趋向无穷。

$$\lim_{n\to\infty}\frac{n}{\log_2 n}=\infty$$

4. 工程启示：在千万级数据上，一个 \(O(n\log n)\) 的排序算法可能几秒完成，而 \(O(n^2)\) 的暴力算法要等到天荒地老；但常数太夸张的 \(O(n\log n)\) 在小数据上也可能输给优化良好的 \(O(n^2)\)。

工程选型时，先看渐进复杂度划掉明显不可行的方案，再结合数据规模、常数因子和空间开销做二次筛选。复杂度分析不给你精确秒表，却给你一张不会迷路的地图。

AI 应用场景

Python 演示

class DynamicArray:    def __init__(self):        self.size = 0        self.capacity = 1     def push(self, value):        if self.size == self.capacity:            old_capacity = self.capacity            self.capacity *= 2            copies = old_capacity        else:            copies = 0        actual = copies + 1        self.size += 1        return actual  def simulate(n):    """    用势能法验证动态数组连续插入的均摊成本。    摊还成本 = 实际成本 + 势能变化    """    size = 0    cap = 1    total_actual = 0    total_amortized = 0     for _ in range(n):        phi_before = 2 * size - cap        if size == cap:            copies = cap            cap *= 2        else:            copies = 0        actual = copies + 1        size += 1        phi_after = 2 * size - cap        amortized = actual + (phi_after - phi_before)        total_actual += actual        total_amortized += amortized     return total_actual, total_amortized  def main():    n = 100000    actual, amortized = simulate(n)    print("实际总成本:", actual)    print("摊还总成本:", amortized)    print("平均摊还成本:", amortized / n)    print("3n 理论界限:", 3 * n)  if __name__ == "__main__":    main()

1. phi_before = 2 * size - cap在操作前计算“时间币余额”，也就是势能值。
2. if size == cap: copies = cap; cap *= 2数组满时执行扩容，复制旧元素需要额外成本。
3. amortized = actual + (phi_after - phi_before)这是势能法的核心公式：摊还成本等于实际成本加势能变化。
4. total_amortized += amortized累加摊还成本，最后与理论界限 3n 对比。

常见误区

面试题