我的算法笔记

例：验证 $T(n) = 2T(n/2) + n$ 的解是 $O(n\log n)$#

猜测： $T(n) \le cn\log n$，对某常数 $c>0$ 和所有 $n$ 足够大成立。

归纳假设： 假设对所有 $m<n$，$T(m) \le cm\log m$ 成立（强归纳法）。

归纳步骤：

要使最后一步 $\le cn\log n$，只需 $-cn+n \le 0$，即 $c \ge 1$。

结论： 取 $c\ge 1$（再单独验证边界情形 $n=1$ 取常数即可吻合），归纳成立，故 $T(n)=O(n\log n)$。

$\blacksquare$

常见陷阱： 直接猜 $T(n)\le cn$（缺少 $\log n$ 因子）会推导失败——归纳步骤会得到 $T(n)\le cn+n$，无法收敛到 $cn$，说明原猜测形式不对，需要调整（这正是代入法”猜测—验证—调整”循环的体现）。

处理边界条件不严格满足的情形#

有时归纳假设 $T(m)\le cm\log m$ 在 $m$ 很小（如 $m=1$，$\log 1=0$）时无法启动归纳。标准技巧： 加强猜测为 $T(n)\le cn\log n - bn$（多减去一个低阶项 $bn$），人为制造出归纳步骤所需的”余量”，再单独验证边界值，使整体猜测自洽。

例：$T(n) = 3T(n/4) + n^2$#

1
层数      节点个数      每节点代价        本层总代价
2
第0层     1            n^2               n^2
3
第1层     3            (n/4)^2           3(n/4)^2 = (3/16)n^2
4
第2层     9            (n/16)^2          9(n/16)^2 = (3/16)^2 n^2
5
...
6
第i层     3^i          (n/4^i)^2         (3/16)^i n^2

叶子层数： 当 $n/4^i = 1$ 时，即 $i = \log_4 n$，到达叶子。

总代价：

这是公比 $3/16 < 1$ 的几何级数，由几何级数求和公式，无穷级数收敛于常数：

结论： $T(n) = O(n^2)$（与主定理情况一直接套用得到的结果一致：$n^{\log_4 3} \approx n^{0.79}$ 是 $f(n)=n^2$ 的低阶，故 $T(n)=\Theta(n^2)$）。

$\blacksquare$

递归树法的价值： 当 $f(n)$ 不满足主定理要求的形式（例如 $f(n)=n/\log n$，既不是任何 $n^{\log_b a \pm \varepsilon}$ 的形式，又不满足正则条件），主定理无法直接套用，但递归树仍然可以展开计算，是比主定理更通用的手段，也是 Akra-Bazzi 方法证明思路的直观来源。

结论#

情况一：若 $f(n)$ 是 $n^{\log_b a}$ 的低阶（无穷小），

$T(n) = \Theta\left(n^{\log_b a}\right)$

情况二：若 $f(n)$ 与 $n^{\log_b a}$ 同阶，

$T(n) = \Theta\left(n^{\log_b a} \cdot \log n\right)$

情况三：若 $f(n)$ 是 $n^{\log_b a}$ 的高阶，

$T(n) = \Theta\left(f(n)\right)$

且满足正则条件：$a f\left(\dfrac{n}{b}\right) \le k f(n)$，对某 $k < 1$，$n$ 足够大

正则条件保证每一层的工作量都不超过某个常数倍的 $f(n)$。

注意： 这三种情况不是穷尽所有可能——$f(n)$ 与 $n^{\log_b a}$ 之间存在”既非多项式地小、又非多项式地大、也不严格同阶”的间隙情形（如相差一个 $\log\log n$ 因子），主定理对这类情形不适用，需要用 Akra-Bazzi 方法或递归树直接计算。

证明#

为简化推导，按惯例假设 $n$ 是 $b$ 的整数次幂，即 $n=b^k$（一般的 $n$ 通过取整处理，结论渐进等价，不影响阶）。

第一步：递归展开

设 $T(1)=\Theta(1)$ 为常数边界，反复代入：

其中 $k=\log_b n$。

关键恒等式：$a^k = a^{\log_b n} = n^{\log_b a}$

证明：两边取 $\log_b$，左边 $=\log_b n \cdot \log_b a$，右边 $=\log_b a \cdot \log_b n$，相等。由 $\log_b$ 单调（一一对应），原等式成立。$\blacksquare$

于是：

接下来分三种情况确定 $g(n)$ 的阶。

情况一：$f(n)=O(n^{\log_b a-\varepsilon})$，某 $\varepsilon>0$

代入：

由 $b^{\log_b a}=a$，得 $a^j b^{-j\log_b a}=a^j a^{-j}=1$，化简为：

求和（等比级数，公比 $b^\varepsilon>1$，由末项主导）：

（用了 $b^{k}=n \Rightarrow b^{k\varepsilon}=n^\varepsilon$）

代回：$T(n)=\Theta(n^{\log_b a})+O(n^{\log_b a})=\Theta(n^{\log_b a})$。$\blacksquare$

情况二：$f(n)=\Theta(n^{\log_b a})$

同样代入：

（与 $j$ 无关，每层同阶）共 $k=\log_b n$ 项求和：

（$\log_b n = \log n/\log b$，$\log b$ 为常数，不改变阶）

代回：$T(n)=\Theta(n^{\log_b a})+\Theta(n^{\log_b a}\log n)=\Theta(n^{\log_b a}\log n)$（第二项渐进更大，主导结果）。$\blacksquare$

情况三：$f(n)=\Omega(n^{\log_b a+\varepsilon})$，且满足正则条件 $af(n/b)\le c f(n)$（$c<1$，$n$ 足够大）

上界：对正则条件归纳应用：

（$j=0$ 显然；设 $j$ 成立，则 $a^{j+1}f(n/b^{j+1}) = a\cdot a^j f(n/b^{j+1}) \le a\cdot c^j f(n/b) \le c^j\cdot a f(n/b) \le c^{j+1}f(n)$）

求和，由 $c<1$ 几何级数收敛：

下界：$g(n)$ 的各项非负，取 $j=0$ 一项即得：

上下界合并：$g(n)=\Theta(f(n))$。

代回：$T(n) = \Theta(n^{\log_b a}) + \Theta(f(n))$。由 $f(n)=\Omega(n^{\log_b a+\varepsilon})$，$f(n)$ 多项式地大于 $n^{\log_b a}$，故第二项主导：

例：验证主定理情况二可以被 Akra-Bazzi 还原#

对 $T(n)=aT(n/b)+f(n)$（单一子问题，对应主定理设定），方程 $a\cdot b^{-p}=1$ 解得 $p=\log_b a$，与主定理中的 $n^{\log_b a}$ 完全吻合，说明 Akra-Bazzi 是主定理的严格推广。

例：非整数分割的递归式#

这种”不均匀分割”的递归式不能直接套主定理（因为两个子问题规模不同），但可以用 Akra-Bazzi：方程为 $(1/3)^p + (2/3)^p = 1$，先猜 $p=1$ 验证：$(1/3)^1 + (2/3)^1 = 1$，恰好成立，所以 $p=1$。代入公式（$f(u)=u$）：

实用判断： 这类”不均匀分割但仍能保证 $O(n\log n)$“的结果，正是快速排序最坏情况之外、各种非均匀分割场景（如带权的分治）复杂度分析的标准工具，第6章快速排序部分提到的”期望情况”分析背后也依赖类似的不均匀分割求和思想。

定义与三个性质#

循环不变式是一个关于循环变量和数据状态的命题 $P$，要用它证明循环正确性，需要验证三个性质：

1. 初始化（Initialization）：循环开始前，$P$ 为真。
2. 保持（Maintenance）：如果某次循环开始时 $P$ 为真，那么这次循环结束后（即下一次循环开始前），$P$ 仍为真。
3. 终止（Termination）：循环结束时，$P$ 仍为真，并且此时 $P$ 加上循环终止的条件，能推出算法的正确性。

这三步本质上是数学归纳法的翻版：初始化对应基础情形，保持对应归纳步骤，终止对应把归纳结论应用到循环退出的那一刻。

例：插入排序的正确性证明#

1
void insertionSort(vector<int>& arr) {
2
    for (int i = 1; i < arr.size(); i++) {
3
        int key = arr[i];
4
        int j = i - 1;
5
        while (j >= 0 && arr[j] > key) {
6
            arr[j + 1] = arr[j];
7
            j--;
8
        }
9
        arr[j + 1] = key;
10
    }
11
}

不变式 $P(i)$： 在外层循环每次开始时（即将处理下标 $i$ 之前），子数组 arr[0..i-1] 是原数组对应位置元素的一个有序排列。

初始化： $i=1$ 时，子数组 arr[0..0] 只有一个元素，单元素数组天然有序，$P(1)$ 成立。

保持： 假设 $P(i)$ 成立，即 arr[0..i-1] 有序。本次循环把 arr[i] 取出存为 key，通过 while 循环把 arr[0..i-1] 中所有大于 key 的元素依次后移一位，再把 key 插入空出的位置。由于 arr[0..i-1] 本身有序，“大于 key 的元素都在末尾连续一段”，后移后再插入 key，得到的 arr[0..i] 仍然有序。于是循环结束、$i$ 自增后，$P(i+1)$ 成立。

终止： 外层循环在 $i = n$（数组长度）时终止，此时 $P(n)$ 成立，即 arr[0..n-1] 整体有序——这正是排序算法要证明的结论。

$\blacksquare$

不变式证明法的通用模板#

1
1. 明确循环变量是什么，不变式P应该用这个变量参数化（如P(i)）
2
2. 初始化：验证循环第一次进入时P成立
3
3. 保持：假设P在某次循环开始时成立，证明执行完循环体（包括变量更新）后，
4
   P在下一次循环开始时依然成立
5
4. 终止：写出循环退出的条件，结合P，推导出算法的最终正确性

适用范围： 不止排序算法，二分查找的”答案一定在 [low, high] 区间内”、图遍历中”已访问集合外的点到起点没有更短路径”（Dijkstra 的正确性论证骨架）等，都是循环不变式的应用实例。

例：归并排序正确性的归纳证明#

命题： 对任意长度为 $n$ 的数组，mergeSort 返回一个有序数组。

基础情形： $n \le 1$ 时，数组天然有序，mergeSort 直接返回，正确。

归纳假设： 假设对所有长度小于 $n$ 的数组，mergeSort 都能正确排序。

归纳步骤： 对长度为 $n$ 的数组，mergeSort 把它分成两个长度均小于 $n$ 的子数组，分别递归调用。由归纳假设，两个子数组的递归调用结果都是有序的。剩下只需证明：两个有序数组用 merge 函数合并后的结果有序——这是一个独立的、不依赖归纳假设的局部性质（可以单独用一个简单的循环不变式证明：merge 每一步都取两个指针当前较小的元素放入结果，结果数组在任意时刻都是已放入元素中最小的那些，按顺序排列）。

因此长度为 $n$ 时 mergeSort 的结果也有序，归纳成立。 $\blacksquare$

两种证明方式的关系： 循环不变式处理的是”同一层级内，状态如何随迭代演化”；数学归纳法处理的是”规模如何随递归层级缩小，子问题的正确性如何传递到父问题”。很多算法的完整正确性证明需要两者配合——例如上面归并排序的证明，“分解+递归”这一层用归纳法，“合并”这一步内部又用了一次局部的循环不变式。

例：动态数组扩容（容量翻倍策略）#

问题： 动态数组初始容量为 1，每次满了就扩容为当前容量的 2 倍（复制所有已有元素），求连续 $n$ 次 push_back 操作的摊还代价。

总代价计算： 设扩容发生在数组大小达到 $1, 2, 4, 8, \dots$ 时。第 $i$ 次扩容（数组大小从 $2^{i-1}$ 变为 $2^i$）需要复制 $2^{i-1}$ 个元素。一共会发生 $\lfloor \log_2 n \rfloor$ 次扩容。

（这是公比为 2 的等比数列求和，末项主导，总和小于末项的 2 倍）

加上 $n$ 次普通插入本身的代价（每次 $O(1)$）：

摊还代价：

结论： 尽管某一次 push_back 触发扩容时最坏要花 $O(n)$ 时间，但 $n$ 次操作的总代价是 $O(n)$，平摊到每次操作只有 $O(1)$。

$\blacksquare$

聚合分析的局限： 它给所有操作分配相同的摊还代价，无法区分”这次操作摊还代价高、那次低”，当一个数据结构上有多种不同代价的操作混合出现时，聚合分析不够精细，这时需要下面两种方法。

例：动态数组扩容的记账法分析#

指定摊还代价： 每次 push_back 的摊还代价记为 3（实际代价是 1，多余的 2 作为信用存到刚插入的这个元素上）。

验证信用不会透支： 每个元素插入时存入 2 点信用。当扩容发生（数组从大小 $m$ 变为 $2m$）时，需要复制 $m$ 个元素，实际代价是 $m$。这 $m$ 个元素中，“上一次扩容之后插入的元素”正好有 $m/2$ 个（因为扩容前数组刚好填满，而上一次扩容后容量是 $m/2$，从 $m/2$ 填到 $m$ 又插入了 $m/2$ 个新元素），每个存有 2 点信用，总信用 $= m/2 \times 2 = m$，恰好够支付这次扩容的复制代价 $m$，信用余额不会变负。

结论： 每次操作摊还代价为常数 3，故 $n$ 次操作总摊还代价为 $O(n)$，由记账法的总账不等式，总实际代价也是 $O(n)$，摊还代价 $O(1)$。

$\blacksquare$

例：栈的 multipop 操作#

问题： 栈支持 push（代价1）、pop（代价1）、multipop(k)（弹出 k 个元素，或栈空则停止，代价 = 实际弹出元素个数）。求 $n$ 次混合操作序列的总代价上界。

朴素分析的问题： multipop(k) 单次最坏代价是 $O(n)$（栈里有 $n$ 个元素时一次弹空），如果直接对每次操作取最坏情况再相加，会得到 $O(n^2)$ 的（过于宽松的）上界。

势函数设计： $\Phi(D) =$ 栈中当前元素个数。显然 $\Phi(D_0) = 0$，且 $\Phi(D_i) \ge 0$ 始终成立，满足势能法的前提条件。

逐操作计算摊还代价：

• push： 实际代价 $c_i = 1$，势能变化 $\Phi(D_i)-\Phi(D_{i-1}) = +1$。摊还代价 $\hat c_i = 1+1 = 2$。
• pop： 实际代价 $c_i = 1$，势能变化 $= -1$。摊还代价 $\hat c_i = 1-1 = 0$。
• multipop(k)： 设实际弹出 $k' = \min(k, |D_{i-1}|)$ 个元素，实际代价 $c_i = k'$，势能变化 $= -k'$。摊还代价 $\hat c_i = k' - k' = 0$。

结论： 每种操作的摊还代价都是 $O(1)$ 常数，因此 $n$ 次任意混合操作的总实际代价：

远好于朴素分析得到的 $O(n^2)$。

$\blacksquare$

应用：并查集路径压缩+按秩合并的复杂度#

第16章并查集一节提到，路径压缩配合按秩合并后，单次 find/union 的摊还复杂度是 $O(\alpha(n))$（$\alpha$ 为反阿克曼函数，增长极慢）。这一结果的严格证明正是通过构造一个基于秩、层级分组的势函数，套用上面同样的"$\sum c_i \le \sum \hat c_i$"框架得到的——证明本身较长（涉及对秩按 $\log^* n$ 量级分组），此处不展开，只指出它在方法论上属于势能法的应用，而不是一种独立的分析技巧。

例：求最大值的下界#

问题： $n$ 个元素中找最大值，最少需要多少次比较？

对手策略： 把每个元素看作一个”尚未被淘汰”的候选者。每次算法比较两个元素 $x, y$ 时，对手回答”$x$ 更大”（任意选一种不矛盾的回答即可），并把 $y$ 标记为”被淘汰”。

论证： 要确定最大值，除了最大值本身，其余 $n-1$ 个元素都必须在某次比较中被判定为”较小”，从而被淘汰——因为如果某个元素从未在任何比较中输给别人，对手可以让它也成为候选的最大值（不矛盾），算法就无法确定唯一的最大值。每次比较最多淘汰 1 个元素（败者），所以至少需要 $n-1$ 次比较才能淘汰掉所有 $n-1$ 个非最大值元素。

与上界的匹配： 朴素的”线性扫描求最大值”算法正好用 $n-1$ 次比较，与这个下界紧密匹配，说明该算法在比较次数意义下已经是最优的。

$\blacksquare$

思路#

每次把数组从中间切开，递归排序两半，再把两个有序数组合并成一个有序数组。

实现#

1
void merge(vector<int>& arr, int l, int mid, int r) {
2
    vector<int> temp;
3
    int i = l, j = mid + 1;
4
    while (i <= mid && j <= r) {
5
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
6
        else temp.push_back(arr[j++]);
7
    }
8
    while (i <= mid) temp.push_back(arr[i++]);
9
    while (j <= r) temp.push_back(arr[j++]);
10
    for (int k = 0; k < temp.size(); k++) arr[l + k] = temp[k];
11
}
12

13
void mergeSort(vector<int>& arr, int l, int r) {
14
    if (l >= r) return;
15
    int mid = l + (r - l) / 2;
16
    mergeSort(arr, l, mid);
17
    mergeSort(arr, mid + 1, r);
18
    merge(arr, l, mid, r);
19
}

复杂度分析#

递归式：

特点： 稳定排序，时间复杂度与输入无关（最好/最坏/平均都是 O(n log n)），但需要额外 O(n) 空间。

思路#

选一个主元（pivot），把数组分成”小于 pivot”和”大于 pivot”两部分，递归排序两部分。

实现（Lomuto 分区）#

1
int partition(vector<int>& arr, int l, int r) {
2
    int pivot = arr[r];
3
    int i = l - 1;
4
    for (int j = l; j < r; j++) {
5
        if (arr[j] < pivot) {
6
            i++;
7
            swap(arr[i], arr[j]);
8
        }
9
    }
10
    swap(arr[i + 1], arr[r]);
11
    return i + 1;
12
}
13

14
void quickSort(vector<int>& arr, int l, int r) {
15
    if (l >= r) return;
16
    int p = partition(arr, l, r);
17
    quickSort(arr, l, p - 1);
18
    quickSort(arr, p + 1, r);
19
}

随机化主元#

问题： 如果数组本身有序或接近有序，固定取最后一个元素作 pivot 会导致每次分区都是 1:(n-1)，退化为 O(n²)。

解决： 随机选 pivot，再交换到末尾，避免对手构造的最坏输入。

1
int randomizedPartition(vector<int>& arr, int l, int r) {
2
    int randIdx = l + rand() % (r - l + 1);
3
    swap(arr[randIdx], arr[r]);
4
    return partition(arr, l, r);
5
}

复杂度分析#

最坏情况（每次分区都是 1:(n-1)）：T(n) = T(n-1) + O(n) ⟹ O(n²)

期望情况（随机主元，分区接近均衡）：O(n log n)

问题#

两个 n×n 矩阵相乘，朴素算法是三重循环，O(n³)：

1
for (int i = 0; i < n; i++)
2
    for (int j = 0; j < n; j++)
3
        for (int k = 0; k < n; k++)
4
            C[i][j] += A[i][k] * B[k][j];

分治思路#

把每个 n×n 矩阵分成 4 个 n/2 × n/2 子矩阵 A11、A12、A21、A22 和 B11、B12、B21、B22。

朴素分治： 需要 8 次子矩阵乘法 + 4 次加法：T(n) = 8T(n/2) + O(n²) ⟹ O(n³)，没有改善。

Strassen 的技巧： 通过 7 次乘法 + 18 次加减法构造出所有子块：

1
M1 = (A11+A22)(B11+B22)
2
M2 = (A21+A22)B11
3
M3 = A11(B12-B22)
4
M4 = A22(B21-B11)
5
M5 = (A11+A12)B22
6
M6 = (A21-A11)(B11+B12)
7
M7 = (A12-A22)(B21+B22)
8

9
C11 = M1+M4-M5+M7    C12 = M3+M5
10
C21 = M2+M4          C22 = M1-M2+M3+M6

复杂度分析#

T(n) = 7T(n/2) + O(n²)，由 Master Theorem：

实用提示： Strassen 常数因子大，且数值稳定性较差，实践中只在矩阵足够大时才有优势。

基础实现#

1
int binarySearch(vector<int>& arr, int target) {
2
    int l = 0, r = arr.size() - 1;
3
    while (l <= r) {
4
        int mid = l + (r - l) / 2;
5
        if (arr[mid] == target) return mid;
6
        else if (arr[mid] < target) l = mid + 1;
7
        else r = mid - 1;
8
    }
9
    return -1;  // 未找到
10
}
11
// 时间：O(log n)，空间：O(1)

复杂度分析： 递归式 $T(n) = T(n/2) + O(1)$，对应 $a=1,b=2,f(n)=O(1)$，$n^{\log_b a}=n^0=1=\Theta(f(n))$，由主定理情况二：

查找左边界（右边界）#

1
arr = [1, 2, 2, 2, 3, 4, 5]  target = 2
2
左边界：下标1
3
右边界：下标3

1
int* lower_bound(int* start, int* end, int find) {
2
    int* lo = start;
3
    int* hi = end;
4
    while (lo < hi) {
5
        int* mid = lo + (hi - lo) / 2;  // 用指针运算，天然防溢出
6
        if (*mid < find) lo = mid + 1;  // mid 及左边都 < find，排除
7
        else             hi = mid;      // mid 可能是答案，保留
8
    }
9
    return lo;  // 第一个 >= find 的位置；都比它小则正好是 end
10
}