第2章 Algorithm Analysis：从代码结构推导增长率

按第3版原章建立渐近数学背景、RAM式计算模型、分析目标和运行时间计算规则，并用四版最大子序列和及三种对数算法核查推导。

从“为什么不能只看一次计时”开始

algorithm analysis（）不是 stopwatch ranking。一次运行时间混合了机器频率、编译器、缓存、输入分布和系统噪声；算法分析先隔离随 N 增长的结构成本，再由实验检查模型是否适合目标机器。

先预测：算法 A 在 N=1000 时用1 ms，算法 B 用5 ms，能否断言 A 更好？若 A 是 quadratic、B 是 linear，当 N 扩大一千倍，A 的工作量大约扩大一百万倍，B 只扩大一千倍；常数优势会被增长阶反转。反过来，小 N 下也不能因为 B 渐近更优就忽略分配、递归和 cache 的固定成本。

官方第3版第2章按四节推进：Algorithm Analysis、Mathematical Background、Model、What to Analyze、Running Time Calculations。顺序不能颠倒：先定义比较语言，再写计算模型，接着指定究竟分析什么，最后才从代码推导。

2.1 Mathematical Background

数学背景（）从量词开始。对最终非负函数 T(N) 与 f(N)：

T(N)=O(f(N))  ⟺  ∃c>0,∃N0,∀N≥N0:T(N)≤cf(N)T(N)=O(f(N)) \iff \exists c>0,\exists N_0,\forall N\ge N_0: T(N)\le c f(N)

O 是 asymptotic upper bound，不是“精确等于”。同一个 3N+2 同时属于 O(N)、O(N²) 和 O(2^N)，但通常选最紧且最简单的上界。lower bound 与 tight bound 分别是：

T(N)=Ω(f(N))  ⟺  ∃c>0,∃N0,∀N≥N0:T(N)≥cf(N)T(N)=\Omega(f(N)) \iff \exists c>0,\exists N_0,\forall N\ge N_0: T(N)\ge c f(N) T(N)=Θ(f(N))  ⟺  T(N)=O(f(N))∧T(N)=Ω(f(N))T(N)=\Theta(f(N)) \iff T(N)=O(f(N)) \land T(N)=\Omega(f(N))

little-o 表示严格更慢的增长：

T(N)=o(f(N))  ⟺  lim⁡N→∞T(N)f(N)=0T(N)=o(f(N)) \iff \lim_{N\to\infty}\frac{T(N)}{f(N)}=0

因此 N 是 o(N log N)，但 N log N 不是 o(N log N)。若极限不存在，不能只凭几张样本图宣称 little-o；第3版勘误也专门修正了对 oscillating ratio 的表述。

运算规则与支配项

若两段代码顺序执行，成本相加，最终由较快增长项支配：

O(f(N))+O(g(N))=O(max⁡(f(N),g(N)))O(f(N))+O(g(N)) = O(\max(f(N),g(N)))

若一段在另一段每次迭代中执行，成本相乘。常数因子和低次项在 asymptotic class 中省略，但精确计数仍可用来检查推导和解释 crossover。

增长率的常见顺序是：

1≺log⁡N≺N≺Nlog⁡N≺N2≺N3≺2N1 \prec \log N \prec N \prec N\log N \prec N^2 \prec N^3 \prec 2^N

这不是说前者在每个 N 都更小；它说比值在充分大 N 后趋向有利方向。工程报告应同时给 complexity class 和目标 N 区间。

2.2 Model

计算模型（）决定证明到底证明了什么。原章采用简化的 RAM-style model：assignment、comparison、简单 arithmetic 和一次 memory access 都按常数时间；程序顺序执行；整数大小足以容纳目标值。

模型有意忽略 cache、branch prediction、allocation、I/O 和 parallelism，优点是能比较算法结构，缺点是结论不能直接替代 wall-clock prediction。若操作本身不是 constant，例如比较长度为 L 的 string，单次 comparison 可能要 O(L)；若整数有 N bits，大整数 multiplication 也不能再当 O(1)。

input size 也必须选对。数组算法通常用元素个数 N；图算法用 vertices V 与 edges E；整数算法应考虑 bit length log value；矩阵算法常用 rows 与 columns。把多个独立维度强行压成 N，会隐藏 sparse/dense 差异。

2.3 What to Analyze

分析什么（）至少包含四项：

  1. 输入尺寸：N、V/E、rows/cols 或 bit length。
  2. 资源：time、extra space、comparisons、allocations 或 I/O。
  3. case：worst、average、best，必要时 amortized 或 expected。
  4. operation contract：search 成功/失败，sort 是否稳定，update 是否计入 rebuild。

worst case 给所有同规模输入的上界，容易陈述也适合 SLA；average case 需要明确概率分布，不能把“看起来随机”当 uniform；best case 只能说明存在幸运输入，通常不足以做容量规划。expected time 是算法内部随机性上的期望，也要区分输入是否 adversarial。

空间分析要区分 input storage 与 auxiliary space。递归调用栈、临时 merge buffer、hash table slack 都是实际资源。返回新容器与原地修改语义不同，不能只比较循环次数。

2.4 Running Time Calculations

运行时间计算（）从代码结构入手。

简单语句、循环与条件

连续语句相加；单循环是每次 body cost 的总和；完整嵌套相乘；依赖循环边界写 summation。条件语句的 worst-case cost 是 test 加两个分支中较大者，而不是把互斥分支相加。

for (int i = 0; i < n; ++i)          // N iterations
    for (int j = 0; j <= i; ++j)     // i+1 iterations
        ++count;

精确 body count 是 N(N+1)/2，所以 Θ(N²)。若第二个循环不是从0到N，而是每次 j *= 2，就应计 log N 次。

最大连续子序列和：同一规格的四种增长阶

作者官方 MaxSumTest.cpp 在同一数组 [4,-3,5,-2,-1,2,6,-2] 上实现四版 maximum contiguous subsequence sum，答案都是11。

  1. cubic 版本枚举 left、right，并再扫描区间求和。
  2. quadratic 版本固定 left 后递增累加，消除第三重重复。
  3. divide-and-conquer 版本取左、右与跨中心最优，递推是 T(N)=2T(N/2)+O(N)。
  4. linear 版本保留当前非负 prefix；一旦 current sum 为负，任何未来区间带上它只会更差。

linear 版本的核心实现是：

int maxSubSum(const std::vector<int>& a) {
    int maxSum = 0;
    int thisSum = 0;
    for (int value : a) {
        thisSum += value;
        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0)
            thisSum = 0;
    }
    return maxSum;
}

这里采用“允许空区间，因此全负数组答案为0”的规格。若题目要求非空区间，initialization 和 reset semantics 都要改变；复杂度相同不代表语义相同。

divide-and-conquer 版本每层处理 O(N) border sums，共 log N 层：

T(N)=2T(N/2)+cN=Θ(Nlog⁡N)T(N)=2T(N/2)+cN=\Theta(N\log N)

运行时间里的对数

binary search 每次保留至多一半区间。区间长度从 N 到1最多减半 k 次，满足 N/2^k 不大于1，所以 k 至少为 log2 N。代码还要保持 invariant：若 x 存在，它始终位于 closed interval [low, high]。

while (low <= high) {
    int mid = low + (high - low) / 2;
    if (a[mid] < x)
        low = mid + 1;
    else if (a[mid] > x)
        high = mid - 1;
    else
        return mid;
}

用 low + (high-low)/2 避免 low+high 溢出。sorted precondition 是算法契约；对未排序数组，循环仍会很快结束，却可能返回错误答案。

Euclid GCD 每轮以 remainder 缩小第二个 operand；快速幂把 exponent 除以2，并在 odd exponent 时补乘一次。二者代码外形不同，但 logarithmic proof 都来自整数参数按固定比例缩小。

long fastPower(long x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    long half = fastPower(x * x, n / 2);
    return n % 2 == 0 ? half : half * x;
}

检查分析，而不是用实验替代分析

推导后可 instrument basic operation count。把 N 按2倍增长，linear count 约2倍，quadratic 约4倍，cubic 约8倍；wall time 若严重偏离，应检查 compiler optimization、cache transition、allocation、overflow 或输入分布。

一套可复核的分析流程

本章回顾

  1. 渐近分析研究资源随输入规模增长的规律，不等于一次机器计时。
  2. O 给上界、Ω 给下界、Θ 给紧确阶，little-o 表示严格更慢增长。
  3. 复杂度结论必须附 input size、cost model、resource 和 case。
  4. 顺序成本相加，嵌套成本相乘，依赖边界写求和，分支取可执行路径。
  5. 最大连续子序列和展示同一语义可有 N³、N²、N log N 和 N 四种实现。
  6. binary search、Euclid GCD 与 fast power 的 logarithm 都来自参数反复缩小。
  7. worst case 不依赖输入分布；average case 必须显式给出概率模型。
  8. instrumentation 用于核查推导与模型，不取代不变量和渐近证明。

名词解释

讨论

评论区加载中…