基础复杂度分析

本教程按“定义→基础计数→循环求和→对数结构→主定理及推广→迭代与递归→平均分析与摊还分析”的顺序展开，旨在帮助读者建立从直观计数到形式化求解、再到序列视角的完整复杂度分析框架，并给出面对具体算法时选择分析工具的依据。

一、什么是算法复杂度？

1.1 从程序到运行时间函数

先约定记号。算法 \(A\) 的输入记作 \(x\)，输入规模记作 \(\lvert x\rvert=n\)；它在输入 \(x\) 上做的基本操作数，或者在某个计算模型下花的时间，记成 \(T_A(x)\)。

同一规模下输入千差万别，最坏情况自然取其中最贵的一个：

\[ T_A(n)=\max_{\lvert x\rvert=n}T_A(x). \]

数组算法的规模一般就是元素个数，图算法的规模往往要同时看顶点数 \(V\) 和边数 \(E\)。规模怎么取，结论的含义就跟着变，这件事后面还会反复出现。

复杂度分析并不打算算出一台机器上的纳秒数——换台机器数字就变了。它只关心 \(n\) 越来越大时，成本以什么速度往上走。

比如某段程序的基本操作数是

\[ T(n)=3n^2+5n+7. \]

\(n\) 还小的时候，平方项、一次项、常数项都还有存在感；\(n\) 到了几万，平方项就把另外两项压得看不见了。所以 \(T(n)=\Theta(n^2)\)。这里的等号不是说操作数真的等于 \(n^2\)，而是说增长速度和 \(n^2\) 只差一个常数倍。

1.2 三种渐近记号

约定 \(f(n)\)、\(g(n)\) 在 \(n\) 足够大时非负。

大 O 管上界。 \(f(n)=O(g(n))\) 的意思是：存在常数 \(c>0\) 和 \(n_0\)，从 \(n_0\) 往后一直有

\[ f(n)\le c,g(n). \]

换句话说，\(f\) 再怎么长，也长不过 \(g\) 的某个常数倍。

大 Ω 管下界。 \(f(n)=\Omega(g(n))\) 的意思是：存在常数 \(c>0\) 和 \(n_0\)，当 \(n\ge n_0\) 时

\[ f(n)\ge c,g(n). \]

大 Θ 是两侧都管。 \(f(n)=\Theta(g(n))\) 当且仅当 \(f(n)=O(g(n))\) 和 \(f(n)=\Omega(g(n))\) 同时成立，也就是 \(f\) 和 \(g\) 在常数因子意义下同阶。

拿 \(3n^2+5n+7\) 来说，它是 \(\Theta(n^2)\)，也是 \(O(n^3)\)，也是 \(\Omega(n^2)\)，但不是 \(\Theta(n^3)\)。说它 \(O(n^3)\) 并没有错，只是丢掉了一些信息，听起来像是我们不知道它其实只有平方那么快。

所以，能给出 \(\Theta\) 就别停在 \(O\)。如果只证出了单侧，写清楚是上界还是下界，比含糊地写一个 \(O\) 要好。

1.3 常见增长速度

增长速度从慢到快排一排：

\[ 1\prec\log n\prec n\prec n\log n\prec n^2\prec n^3\prec c^n\prec n!, \]

\(c>1\) 是常数，\(\prec\) 读作“比……长得慢”。这张表值得记熟，比较两个算法时，多数时候只是在表上比位置。

对数有个方便之处：底数可以随便换。\(b>1\) 固定时，

\[ \log_b n=\frac{\ln n}{\ln b}=\Theta(\log n), \]

换底只多乘一个常数，渐近阶不受影响。

真正容易出错的是“规模”怎么定义。整数 \(N\) 用二进制写出来只有 \(\Theta(\log N)\) 位。一个循环跑 \(N\) 次的程序，按数值看是线性的，按输入长度 \(m=\Theta(\log N)\) 看却是 \(\Theta(2^m)\)。伪多项式时间说的就是这种算法：数值上像多项式，按输入长度算却是指数。

1.4 时间复杂度与空间复杂度

时间复杂度数操作，空间复杂度数内存，两边分开算。

空间这边有个坑：得先说清算不算输入本身。通常只算辅助空间，但如果题目要求“含输入的总空间”，结论可能完全不同。

递归函数就是例子。局部变量也许只有几个，但每一层调用都要用到栈。深度为 \(d\)、每层栈帧占用常量空间，栈上就是 \(O(d)\)。归并排序这类递归，这一项不能当成零。

二、基础计数

分析程序的第一步不是套公式，而是决定数什么。一般不必细到每条机器指令，把同类操作的成本都算作常数就够了。

2.1 顺序执行：复杂度相加

1
2
3
4
5
6
7
8
9

void example(size_t n) {
    for (size_t i = 0; i < n; ++i) {
        /* O(1) work */
    }

    for (size_t j = 0; j < n; ++j) {
        /* O(1) work */
    }
}

两个循环各跑 \(n\) 次，接在一起，总量还是 \(n\) 的量级：

\[ T(n)=\Theta(n)+\Theta(n)=\Theta(n). \]

常数 2 在这里无关紧要，重要的是两个线性段加起来仍然是线性。

一般地，两段连续代码分别花 \(f(n)\)、\(g(n)\)，总时间就是 \(f(n)+g(n)\)。只关心上界时，对非负函数有

\[ O(f(n))+O(g(n))=O(\max{f(n),g(n)}). \]

所以一段 \(O(n^2)\) 后面接一段 \(O(n)\)，总归是 \(O(n^2)\)，慢的那段说了算。

2.2 单层循环

1
2
3
4
5

void linear_loop(size_t n) {
    for (size_t i = 0; i < n; ++i) {
        /* O(1) work */
    }
}

循环体跑满 \(n\) 遍。设初始化之类的额外开销是 \(c_1\)，每遍循环体是 \(c_2\)，于是

\[ T(n)=c_1+c_2n=\Theta(n). \]

如果循环跑 \(k(n)\) 遍、循环体是 \(\Theta(1)\)，总时间就是 \(T(n)=\Theta(k(n))\)。要看的从来不是 for 长什么样，而是循环变量怎么走。

2.3 嵌套循环

情况 A：内外层范围独立

1
2
3
4
5
6
7

void nested_loop(size_t n) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            /* O(1) work */
        }
    }
}

外层 \(n\) 次，内层每轮也是 \(n\) 次，乘起来：

\[ T(n)=n\cdot n=\Theta(n^2). \]

情况 B：内层依赖外层变量

1
2
3
4
5
6
7

void triangular_loop(size_t n) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < i; ++j) {
            /* O(1) work */
        }
    }
}

内层每轮分别执行 \(0,1,2,\ldots,n-1\) 次，加起来是等差数列：

\[ T(n)=\sum_{i=0}^{n-1}i=\frac{n(n-1)}{2}=\Theta(n^2). \]

两个程序最后都落在平方，但过程不一样。前者每轮一样重，后者越往后越重；平均下来是 \(n^2/2\)，仍然是同阶。写求和式而不是直接写个 \(n^2\)，循环一复杂就能看出区别。

2.4 条件分支

1
2
3
4
5
6
7
8
9

void conditional(size_t n) {
    if (n < 10) {
        /* O(1) */
    } else {
        for (size_t i = 0; i < n; ++i) {
            /* O(1) */
        }
    }
}

\(n\ge10\) 时走线性分支，所以最坏情况是 \(\Theta(n)\)。

若两个分支分别花 \(T_1(n)\)、\(T_2(n)\)，条件判断本身是常数时间，那么

\[ T(n)=O(\max{T_1(n),T_2(n)}). \]

这是上界，由较贵的那个分支决定。要谈平均情况，得先知道输入有多大概率走进各分支，光看代码给不出这个数。

2.5 一个更通用的计数方法

设第 \(i\) 类基本操作执行 \(c_i(n)\) 次，单次成本是常数 \(w_i\)，总成本就是

\[ T(n)=\sum_i w_i c_i(n). \]

常数权重不影响渐近阶，问题于是归结为各个 \(c_i(n)\) 怎么数。后面所有的循环求和，都是这个式子的具体化。

三、循环求和

把循环翻译成求和，是复杂度分析里最实用的一步。单个循环好办，麻烦多半出在循环次数跟着变量走的时候。

3.1 算术级数

最常用的是

\[ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\Theta(n^2). \]

例如：

1
2
3
4
5
6
7

void quadratic_work(size_t n) {
    for (size_t i = 1; i <= n; ++i) {
        for (size_t j = 0; j < i; ++j) {
            /* O(1) work */
        }
    }
}

内层执行 \(1,2,\ldots,n\) 次，加起来就是上式：

\[ T(n)=\sum_{i=1}^{n}i=\Theta(n^2). \]

要是循环体每轮做 \(i^2\) 个单位操作，和就换成平方和：

\[ T(n)=\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}=\Theta(n^3). \]

两个例子的套路一样：先看单轮成本，再对轮数求和。反过来先猜一个总复杂度、再找理由，很容易在稍复杂的循环上翻车。

3.2 几何级数

几何级数

\[ \sum_{i=0}^{k}r^i=\frac{r^{k+1}-1}{r-1},\qquad r\ne 1 \]

在 \(r>1\) 时由最后一项主导，\(\sum_{i=0}^{k}r^i=\Theta(r^k)\)；在 \(r\in(0,1)\) 时由首项主导，和收敛到常数，即 \(\Theta(1)\)。

1
2
3
4
5

void geometric_loop(size_t n) {
    for (size_t m = n; m > 0; m /= 2) {
        /* O(1) work */
    }
}

每轮 \(m\) 减半。忽略取整，第 \(k\) 轮时 \(m_k\approx n/2^k\)；等 \(k\) 超过 \(\log_2 n\)，\(m\) 就降到 0，循环结束。精确次数是 \(\lfloor\log_2 n\rfloor+1\)（\(n\ge1\)），所以

\[ T(n)=\Theta(\log n). \]

和 2.2 的线性循环对照一下：那边循环变量每轮加一，这边每轮乘 \(1/2\)。加一得到线性，乘固定比例得到对数，这是两种完全不同的节奏。

3.3 调和级数

调和级数

\[ H_n=\sum_{i=1}^{n}\frac1i \]

看着像要发散，其实只长到对数那么慢。用积分夹一下就清楚：

\[ \int_1^{n+1}\frac{dx}{x}\le H_n\le 1+\int_1^n\frac{dx}{x}. \]

两端都是 \(\Theta(\log n)\)，所以 \(H_n=\Theta(\log n)\)。

这类和常出现在平均分析里，快速排序的平均比较次数就带着 \(H_n\)。举个例子，某算法第 \(i\) 个阶段的成本约为 \(n/i\)，总成本就是

\[ T(n)=\sum_{i=1}^{n}\frac{n}{i}=nH_n=\Theta(n\log n). \]

这里的 \(n/i\) 是模型里的抽象成本，不必真对应某段循环的整数次数。

3.4 嵌套循环的本质是求和，不是乘法

看这个：

1
2
3
4
5
6
7

void halving_inner(size_t n) {
    for (size_t m = n; m > 0; m /= 2) {
        for (size_t j = 0; j < m; ++j) {
            /* O(1) work */
        }
    }
}

外层 \(\Theta(\log n)\) 轮，各轮内层大约跑 \(n,n/2,n/4,\ldots\) 次。有人会顺手写成“对数层乘每层 \(n\)”，得到 \(n\log n\)。这个答案是错的，因为每层的量并不一样：

\[ \begin{aligned} T(n)&=\sum_{k=0}^{\lfloor\log_2 n\rfloor}\Theta\left(\frac{n}{2^k}\right)\ &=\Theta(n). \end{aligned} \]

几何递减的和由第一层主导，后面的层加起来还没有第一层多。层数是对数级，不代表总时间里有对数。

作为对比，内层如果每轮都老老实实跑 \(\Theta(n)\) 次，那才是

\[ T(n)=\Theta(n)\cdot\Theta(\log n)=\Theta(n\log n). \]

常见模式整理成表，分析时可以先对着表找：

四、对数结构

凡是“每轮把规模乘上一个小于 1 的常数”的结构，都容易长出 \(\log n\)。

设每轮后规模变成原来的 \(1/b\)（\(b>1\)），\(k\) 轮之后

\[ n_k=\frac{n}{b^k}. \]

规模降到常数（\(n/b^k\le c\)）时，正好是

\[ k\ge\log_b(n/c)=\Theta(\log n). \]

只要每轮成本是 \(O(1)\)、规模按固定比例缩，总时间一般就是 \(\Theta(\log n)\)。

4.1 二分查找

前提是数组已经排好序。每次拿中间元素跟目标比，不管结果如何，总有一半左右的候选位置可以排除。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdbool.h>
#include <stddef.h>

bool binary_search(const int *a, size_t n, int key) {
    size_t lo = 0;
    size_t hi = n;  /* 搜索区间为 [lo, hi) */

    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;

        if (a[mid] < key) {
            lo = mid + 1;
        } else if (a[mid] > key) {
            hi = mid;
        } else {
            return true;
        }
    }

    return false;
}

半开区间 \([lo,hi)\) 让空数组自然对应 lo == hi。另外，size_t 下写 hi = n - 1，遇到 \(n=0\) 会直接下溢成一个大数，半开区间省了这个麻烦。

设第 \(k\) 轮候选区间长度为 \(m_k\)，每轮至多减半：

\[ m_{k+1}\le\frac{m_k}{2}, \]

于是 \(m_k\le n/2^k\)。要缩到空，\(k\) 只需到对数级，所以：

• 最坏 \(\Theta(\log n)\)；
• 额外空间 \(\Theta(1)\)；
• 最好情况第一次就命中，\(\Theta(1)\)。

端点开闭、取整方向会影响具体比较几次，但改不了这个阶。

4.2 对数复杂度不一定来自单个循环

递归里也能长出 \(\log n\)：每层把规模砍一半，树就有 \(\Theta(\log n)\) 层。

但深度不等于总时间。归并排序的树也是 \(\log n\) 层，可每层都要做线性合并，总时间就成了 \(n\log n\)。递推式或递归树要做的，就是把这两件事分开：几层，每层多少。

五、主定理及其推广

分治算法的运行时间天然写成递推式：把规模 \(n\) 的问题切成 \(a\) 个 \(n/b\) 的子问题，切开和合并这些非递归部分花 \(f(n)\)。

\[ T(n)=aT(n/b)+f(n). \]

这里 \(a\ge1\)、\(b>1\) 是常数，另外还需要基本情形，比如 \(T(1)=\Theta(1)\)。

主定理回答的是：子问题个数、缩减比例、额外工作这三个量，谁说了算。

5.1 主定理

记

\[ d=\log_b a. \]

这个指数有两个用处：\(a=b^d\)，且 \(a(n/b)^d=n^d\)。也就是说，如果每一层不论深浅都花 \(n^d\) 的“标准成本”，各层就是齐平的；总时间取决于递归树是往叶子倾斜，还是往根倾斜。

设递推满足主定理的标准条件，三种情形如下。

情形一：递归部分更重。 存在常数 \(\varepsilon>0\) 使

\[ f(n)=O(n^{d-\varepsilon}), \]

则

\[ T(n)=\Theta(n^d). \]

\(f\) 比 \(n^d\) 低了一个多项式量级。越往深处子问题越多，叶子那层的总量反过来压过上层的工作。

比如 \(T(n)=4T(n/2)+n\)。这里 \(a=4\)、\(b=2\)，所以 \(d=\log_2 4=2\)；\(f(n)=n\) 比 \(n^2\) 低一阶，直接得 \(T(n)=\Theta(n^2)\)。

情形二：两边持平。 若

\[ f(n)=\Theta(n^d), \]

则每层工作量差不多，总时间等于层数乘以每层：

\[ T(n)=\Theta(n^d\log n). \]

带对数修正的版本是：若 \(f(n)=\Theta(n^d\log^k n)\)（\(k\ge0\)），则

\[ T(n)=\Theta(n^d\log^{k+1}n). \]

典型例子 \(T(n)=2T(n/2)+n\)，这里 \(d=\log_2 2=1\)，\(f(n)=n\) 正好和 \(n^d\) 同阶，于是 \(\Theta(n\log n)\)。递归树每层都是 \(n\) 的总账，树高 \(\log_2 n\)，乘起来就是了。

情形三：额外工作更重。 若存在 \(\varepsilon>0\) 使

\[ f(n)=\Omega(n^{d+\varepsilon}), \]

并且还要满足正则性条件：存在常数 \(c\in[0,1)\)，对充分大的 \(n\) 有 \(af(n/b)\le cf(n)\)，则

\[ T(n)=\Theta(f(n)). \]

正则性条件管的是“下一层的总工作是不是真的按比例缩小”。只比较多项式阶有时候会骗人，加上这一条才稳。

比如 \(T(n)=2T(n/2)+n^2\)。这里 \(d=1\)，\(f(n)=n^2\)，且

\[ 2f(n/2)=2\left(\frac{n}{2}\right)^2=\frac{n^2}{2}, \]

取 \(c=1/2\) 就满足条件，所以 \(T(n)=\Theta(n^2)\)。

5.2 主定理的使用边界

主定理只认

\[ T(n)=aT(n/b)+f(n) \]

这一种形状：所有子问题按同一个比例缩。

\[ T(n)=T(n/3)+T(2n/3)+n \]

两个子问题规模不同，直接套不进去；\(T(n)=T(n-1)+n\) 每次只减一个常数，也不在适用范围。这类递推老老实实展开、画树，或者上 Akra–Bazzi。

5.3 Akra–Bazzi 定理

Akra–Bazzi 就是为“子问题不一样大”准备的。考虑

\[ T(x)=g(x)+\sum_{i=1}^{k}a_iT\bigl(b_ix+h_i(x)\bigr). \]

常用的条件是：

• \(a_i>0\)、\(b_i\in(0,1)\) 是常数；
• 基本情形够多，递推有定义；
• 扰动小，\(h_i(x)=O(x/\log^2 x)\)；
• \(g(x)\) 非负，且满足正则性条件——标准表述里要求 \(|g’(x)|\) 被某个多项式界住。

令 \(p\) 是方程

\[ \sum_{i=1}^{k}a_ib_i^p=1 \]

的唯一实根（\(b_i\) 都小于 1，左边随 \(p\) 严格递减，根只有一个）。那么

\[ T(x)=\Theta\left(x^p\left[1+\int_1^x\frac{g(u)}{u^{p+1}},du\right]\right). \]

主定理里那个基准是 \(\log_b a\)，这里换成了 \(p\)；因为各子问题比例不同，\(p\) 得由所有 \(b_i\) 一起定。

推导示例：两个不同规模的子问题。 拿

\[ T(n)=T(n/3)+T(2n/3)+n \]

试一遍。先解特征方程

\[ \left(\frac13\right)^p+\left(\frac23\right)^p=1. \]

左边单调，根唯一。代 \(p=1\) 正好成立（\(1/3+2/3=1\)），所以 \(p=1\)。

这里 \(g(u)=u\)，代入积分：

\[ \begin{aligned} T(n)&=\Theta\left(n\left[1+\int_1^n\frac{u}{u^2},du\right]\right)\ &=\Theta\left(n\left[1+\int_1^n\frac1u,du\right]\right)\ &=\Theta(n(1+\ln n)), \end{aligned} \]

也就是 \(\Theta(n\log n)\)。

这个例子真正要紧的是顺序：先解 \(p\)，再积分。两个规模不同的子问题，不能先当成同规模往里套主定理。

5.4 如何选择递推分析工具

六、迭代与递归

“迭代”和“递归”在这门课里有两个用法，容易混：一是程序怎么写（循环，还是自己调用自己），二是怎么解递推式（迭代展开法）。两者有联系，但不是一回事。

6.1 迭代展开法

以

\[ T(n)=T(n/2)+n,\qquad T(1)=\Theta(1) \]

为例。第一次把 \(T(n/2)\) 按递推展开：

\[ T(n)=T(n/4)+\frac n2+n. \]

一直代到第 \(k\) 次：

\[ T(n)=T(n/2^k)+n\sum_{j=0}^{k-1}\frac1{2^j}. \]

子问题降到常数，也就是

\[ \frac{n}{2^k}=\Theta(1)\quad\Longrightarrow\quad k=\Theta(\log n). \]

后半截是几何级数，\(n\sum_{j=0}^{k-1}2^{-j}=\Theta(n)\)；前面 \(T(1)\) 是常数。所以

\[ T(n)=\Theta(n). \]

展开法就三步：写出第 \(k\) 次的一般式，用基本情形定 \(k\)，再把剩下的和算出来。中间哪一步写错，最后都会歪。

6.2 另一个展开例子（规模减1）

换成

\[ T(n)=T(n-1)+n,\qquad T(1)=\Theta(1). \]

一路展开：

\[ T(n)=T(1)+\sum_{i=2}^{n}i, \]

所以

\[ T(n)=\Theta(1)+\frac{n(n+1)}{2}-1=\Theta(n^2). \]

每次只减常数，深度就是 \(\Theta(n)\)；每层减半，深度是 \(\Theta(\log n)\)。这两个深度差得很远，是很多递推求解的第一步判断。

6.3 递归树法

对

\[ T(n)=2T(n/2)+n \]

画树。根层一个 \(n\)；下一层两个 \(n/2\)，加起来还是 \(n\)；再下一层四个 \(n/4\)，还是 \(n\)。每层都恰好 \(n\)，树高约 \(\log_2 n\)，所以

\[ T(n)=\sum_{j=0}^{\lfloor\log_2 n\rfloor}\Theta(n)=\Theta(n\log n). \]

不用把叶子成本抠得很精确。层数说得清、每层总量的上下界说得清，阶就出来了。

6.4 代入法

代入法（也叫替换法）是先猜后证：先从展开或递归树看出一个界，再用归纳法把它坐实。

对 \(T(n)=2T(n/2)+n\)，猜测 \(T(n)=O(n\log n)\)。归纳假设对更小的规模成立，即

\[ T(n/2)\le c\frac n2\log_2(n/2), \]

那么

\[ \begin{aligned} T(n)&=2T(n/2)+n\ &\le cn\log_2(n/2)+n\ &=cn\log_2 n-cn+n\ &\le cn\log_2 n, \end{aligned} \]

只要 \(c\ge1\)。基本情形得单独交代：\(n=1\) 时 \(n\log_2 n=0\)，猜的界在这儿不成立，所以通常从 \(n\ge2\) 起做归纳，取足够大的 \(c\) 把那几个初值验证掉。

这样得到的是上界 \(O(n\log n)\)。要写 \(\Theta\)，还得补一个下界；只有上界的话，说 \(\Theta\) 是不严谨的。

6.5 递归程序的时间复杂度与空间复杂度

递归深度先决定栈有多深，再和每层的工作量一起决定总时间。两者不要混着说。

归并排序：每次对半切，递归排好两半，再线性合并。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

static void merge_sort_rec(
    int *a,
    int *tmp,
    size_t lo,
    size_t hi
) {
    if (hi - lo <= 1) {
        return;
    }

    size_t mid = lo + (hi - lo) / 2;

    merge_sort_rec(a, tmp, lo, mid);
    merge_sort_rec(a, tmp, mid, hi);

    size_t i = lo;
    size_t j = mid;
    size_t k = lo;

    while (i < mid && j < hi) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }

    while (i < mid) {
        tmp[k++] = a[i++];
    }

    while (j < hi) {
        tmp[k++] = a[j++];
    }

    for (k = lo; k < hi; ++k) {
        a[k] = tmp[k];
    }
}

bool merge_sort(int *a, size_t n) {
    if (n == 0) {
        return true;
    }

    if (a == NULL || n > SIZE_MAX / sizeof(int)) {
        return false;
    }

    int *tmp = malloc(n * sizeof(*tmp));
    if (tmp == NULL) {
        return false;
    }

    merge_sort_rec(a, tmp, 0, n);

    free(tmp);
    return true;
}

两个递归调用各处理一半，合并是线性的，于是

\[ T(n)=2T(n/2)+\Theta(n). \]

主定理情形二直接给 \(T(n)=\Theta(n\log n)\)。

空间上，辅助数组是 \(\Theta(n)\)，递归栈是 \(\Theta(\log n)\)。按“除输入之外的辅助空间”算，总数还是 \(\Theta(n)\)，栈那项被数组压过去了。

七、平均分析与摊还分析

两种分析都在看“多次操作”，但回答的问题不同。平均分析问：输入按某个分布随机取时，期望成本是多少。摊还分析问：不管输入长什么样，一串操作的总成本能控制到多少。

7.1 平均分析

设 \(X_n\) 是按某个分布抽出的规模为 \(n\) 的随机输入，平均时间是

\[ \mathbb{E}[T(X_n)]=\sum_{\lvert x\rvert=n}\Pr(X_n=x)T(x). \]

公式本身就说明了问题：不给分布，“平均”二字没有定义。很多所谓“平均 \(O(n)\)”的说法，其实默认了均匀分布。

线性查找。 数组长 \(n\)，目标一定存在且等概率落在任一位置。若目标在第 \(i\) 位，要比较 \(i\) 次，于是

\[ \begin{aligned} \mathbb{E}[C_n]&=\frac1n\sum_{i=1}^{n}i\ &=\frac{n+1}{2}\ &=\Theta(n). \end{aligned} \]

最坏是目标在最后，\(n\) 次；最好是第一次就中。三档分别是

\[ \Theta(1),\qquad\Theta(n),\qquad\Theta(n). \]

如果目标可能不存在，那就得扫完 \(n\) 个才敢下结论，平均结论也随之改变。

7.2 随机化算法与平均情况并不等同

平均情况假设输入服从某个分布；随机化算法则是在固定输入上自己掷骰子。

随机选枢轴的快排，期望时间 \(\Theta(n\log n)\)——这个期望是对算法内部的随机选择取的。碰上精心构造的最坏输入，加上运气差，仍可能退到 \(\Theta(n^2)\)。

所以看到“期望”两个字，先问一句：随机性来自输入，还是来自算法本身？

7.3 摊还分析

摊还分析（amortized analysis）算的是一串操作的总账。若 \(m\) 次操作的实际成本 \(c_1,\ldots,c_m\) 满足

\[ \sum_{i=1}^{m}c_i=O(m), \]

就说这类操作的摊还成本是 \(O(1)\)。

这不代表每次操作都只花常数时间。某一次可能很贵，只要贵的次数足够少，总账仍然平。

7.4 动态数组扩容

动态数组满了就把容量翻倍，再把旧元素搬过去。平时插入是一次写入，满了就得复制一整片。

连续插入 \(n\) 个元素，各次扩容复制的量是 \(1,2,4,\ldots,2^k\)，其中 \(n\in(2^k,2^{k+1}]\)。这些复制加起来

\[ 1+2+4+\cdots+2^k=2^{k+1}-1\le 2n. \]

每次插入自己还要写一次，共 \(n\) 次，所以总成本

\[ C(n)=O(n), \]

摊到每次插入就是 \(O(1)\)。贵的那次确实贵，但它隔得足够远。

这里的账按常见的数据结构模型算：一次扩容记作与旧数组长度成正比的成本，不去纠结具体分配器在那一刻的真实耗时。

7.5 聚合分析、记账法与势能法

三种方法，问的是同一件事，只是记账方式不同。

聚合分析。 直接把 \(m\) 次操作的总成本算出来，证明它是 \(O(m)\)，摊还成本自然就是 \(O(1)\)。动态数组的几何扩容就是这么做：复制会发生，但总量被 \(O(m)\) 卡住。

记账法。 给每类操作定一个“收费”。便宜的多收一点，差额存成信用，留给以后贵操作用。这只是一个证明用的账本，不是真钱；规矩是信用不能为负，且所有实际成本都被覆盖。

势能法。 把数据结构的状态记作 \(D_i\)，用一个非负的势函数 \(\Phi(D_i)\) 表示“攒下的余量”。第 \(i\) 次操作实际花 \(c_i\)，定义摊还成本

整个序列求和，中间的势能差一项项消掉：

这就是望远镜求和。若初始势能为零、过程中势能始终非负，则

所以只要每次的摊还成本都是 \(O(1)\)，总实际成本就是 \(O(m)\)。

例子：支持批量删除的栈。 栈有 push、pop，以及 multipop(k)：最多弹出 \(k\) 个元素，弹到空为止。

multipop(k) 一次可能花 \(\Theta(k)\)，单看这次绝不是 \(O(1)\)。但把势能取成栈里的元素个数（压入加一、弹出减一）之后：

• 每个元素只被压入一次、弹出一次；
• 所有 multipop 删掉的总数不会超过压入总数；
• \(m\) 次操作合起来，总工作量是 \(O(m)\)。

于是摊还成本是 \(O(1)\)，哪怕某一次 multipop 线性时间跑完。

7.6 平均分析与摊还分析的根本区别

把“期望 \(O(1)\)”和“摊还 \(O(1)\)”当成同义词，是常见的误解。前者是概率意义上的平均，后者是对任意操作序列总成本的保证；一个依赖分布，一个连概率都不需要。