1.4 Analysis of Algorithms：从计时实验到成本模型

1.4 · Analysis of Algorithms覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“1.4 · Analysis of Algorithms”如何把计时实验、数学模型、增长数量级、内存模型和更快算法放进同一可证伪预测
能逐项核对算法分析、科学方法、数学模型、增长数量级、设计更快算法、内存使用，并区分作者站内容与本页独立补充
能按“T(N) ≈ aN^b；doubling ratio ≈ 2^b；ThreeSum 暴力模型约为 N^3 / 6 次三元检查”手算一个最小输入，逐步检查“比较实现时必须固定输入分布、机器、JVM、预热、计数单位与正确性预言机”
能注入“只取最快一次墙钟时间，或在扩大 N 时同时改变数据分布与实现版本”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“1·4 · Analysis of Algorithms”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“1·4 · Analysis of Algorithms”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“1·4 · Analysis of Algorithms”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：1.4 · Analysis of Algorithms

1. 算法分析：在本页通过“提出增长假设”连接解释、交互状态和练习验收。
2. 科学方法：在本页通过“选择基本操作”连接解释、交互状态和练习验收。
3. 数学模型：在本页通过“做倍增实验”连接解释、交互状态和练习验收。
4. 增长数量级：在本页通过“拟合幂律模型”连接解释、交互状态和练习验收。
5. 设计更快算法：在本页通过“检查残差与反例”连接解释、交互状态和练习验收。
6. 内存使用：在本页通过“提出增长假设”连接解释、交互状态和练习验收。

从“跑了0.6秒”开始追问

算法分析（analysis of algorithms）不等于把loop数换成Big-O。一次运行0.6秒只描述一个program、一个input、一个machine和一个时刻；要预测N翻倍、输入分布改变或implementation替换后的结果，必须提出可检验模型。

先预测ThreeSum在N从1000翻到2000时会慢2倍、4倍还是8倍。若dominant work与N的三次方成正比，ratio趋近8；但小N计时可能被JVM warm-up、timer resolution和I/O淹没。正确做法不是挑一个“像8”的结果，而是控制实验、连续doubling、观察稳定区间并用新数据尝试推翻hypothesis。

官方1.4按 Scientific method、Observations、Mathematical models、Designing faster algorithms、Coping with dependence on inputs、Memory usage 展开，并用 ThreeSum、Stopwatch、DoublingRatio 和 ThreeSumFast 建立完整证据链。

1.4.1 Scientific method：模型必须允许被证伪

科学方法（scientific method）要求experiment可重放，measurements可比较，hypothesis足够具体。对running time，常用模型是：

T(N)\sim aN^b

其中N是明确的input-size measure，a吸收machine、language与implementation constants，b描述dominant growth。符号 ~ 表示ratio趋近1，不是所有N都精确相等。若observations持续偏离，应该修正模型或input definition，而不是把偏差归为“电脑不稳定”。

Time experiment至少记录source revision、JVM/flags、machine load、input generator与seed、warm-up、repetitions和aggregation方式。只计核心algorithm还是包含file I/O也必须说明。Official Stopwatch 测wall-clock；它适合end-to-end observation，但会包含scheduling与其他system effects。

1.4.2 Observations：用doubling experiment找稳定信号

观察（observations）先回答“实际发生了什么”。Official DoublingRatio.timeTrial 生成N个随机六位整数，只计 ThreeSum.count，然后输出当前time与前一size的ratio。

public static double timeTrial(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
        a[i] = StdRandom.uniformInt(-1_000_000, 1_000_000);
 
    Stopwatch timer = new Stopwatch();
    int ignored = ThreeSum.count(a);
    return timer.elapsedTime();
}

若time model是 aN^b，doubling消去coefficient：

\frac{T(2N)}{T(N)}\sim 2^b, \qquad b\approx\log_2\!\left(\frac{T(2N)}{T(N)}\right)

Official sample在足够大N后ratio接近8，支持cubic hypothesis。小time四舍五入为0时ratio无意义；随机inputs也让每轮work outcome和cache behavior略不同。应重复多次，使用median或distribution，并让test足够长以超过timer granularity。

1.4.3 Mathematical models：先数关键operation

数学模型（mathematical models）把code structure变成可核查count。ThreeSum使用indices i < j < k，每个合法triple做一次sum-equality test，因此frequency恰为：

\binom{N}{3} =\frac{N(N-1)(N-2)}{6} \sim\frac{N^3}{6}

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (a[i] + a[j] + a[k] == 0)
                count++;

成本模型（cost model）在这里选sum comparison。Assignment、loop increments和bounds checks也发生，但同属cubic leading order；若要预测constant a，可对各instruction frequency和machine cost进一步建模。

增长数量级（order of growth）帮助比较scalability，却不能替代contract。Logarithmic、linear、N log N、quadratic、cubic在N小时差距不明显，规模增大后迅速分离。

1.4.4 Designing faster algorithms：改变operation count结构

设计更快算法（designing faster algorithms）不是把同一triple loop写得更短，而是利用ordering重构problem。ThreeSumFast 先sort，再枚举i/j，用binary search找 -(a[i]+a[j])，并要求found index大于j，避免同一triple重复计数。

Arrays.sort(a);
if (containsDuplicates(a))
    throw new IllegalArgumentException("array contains duplicate integers");
 
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        int k = Arrays.binarySearch(a, -(a[i] + a[j]));
        if (k > j) count++;
    }
}

Pair count是quadratic，每次binary search logarithmic，加sorting后：

T_{fast}(N)=O(N\log N)+O(N^2\log N)=O(N^2\log N)

这是真正的growth improvement，但新preconditions必须进入correctness comparison。Current official code拒绝duplicates；原始ThreeSum按index triples可处理duplicates。两者都明确忽略integer overflow，-(a[i] + a[j]) 也可能overflow。若生产需求允许任意int与duplicates，应使用long intermediate并设计multiplicity-aware counting，不能只比较sample counts。

1.4.5 Coping with dependence on inputs

Input dependence说明同一N不一定同一time。Quicksort后续会依赖partition quality，symbol-table search依赖key distribution，graph algorithms依赖V/E structure。ThreeSum的triple enumeration count固定，但matches数量影响count increments和branch behavior；faster version还受sort/binary-search path与duplicates policy影响。

Input model必须显式。Average-case claim要给probability distribution；expected time要说明randomness来自input还是algorithm；worst case则对所有合法inputs成立。Random test generator用于sampling，不自动代表真实workload。

处理dependence的实用方式包括：报告best/average/worst bounds；按多个structure parameters建模；对真实traces与synthetic adversarial cases分层；用operation counts分离algorithm变化与machine noise。

1.4.6 Memory usage：把objects、references与alignment计入模型

内存使用（memory usage）也需要cost model。Primitive sizes、reference width、object header、array header与8-byte alignment决定近似bytes；linked representation还为每个item支付node overhead。

在一个简化64-bit model中，可写：

M(N)\approx M_{header}+N\cdot M_{item}+M_{padding}

但reference array只包含references，不包含被引用objects；shared objects不能重复全算，reachable graph也可能有cycles。Compressed ordinary object pointers、JVM implementation与alignment会改变常数，最终应使用profiler或instrumentation验证。Space complexity关心随N增长，capacity strategy则同时影响constant factor与峰值。

统一验收：让measurement与model相互约束

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“1.4 · Analysis of Algorithms”的两个最小情境间切换，再逐项选择正式概念。预测“T(N) ≈ aN^b；doubling ratio ≈ 2^b；ThreeSum 暴力模型约为 N^3 / 6 次三元检查”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

1.4 · Analysis of Algorithms：对象、操作与不变量

把计时实验、数学模型、增长数量级、内存模型和更快算法放进同一可证伪预测

选择最小情境

切换正式概念

倍增实验: 固定生成器，把 N 从 1k 依次翻倍到 8k
当前观察: analysis of algorithms：比值趋近 2、4、8 时分别提示线性、平方、立方主导项

T(N) ≈ aN^b；doubling ratio ≈ 2^b；ThreeSum 暴力模型约为 N^3 / 6 次三元检查

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

算法分析：在实验 1 中指出对应状态，并写出一个通过条件。
科学方法：在实验 2 中指出对应状态，并写出一个通过条件。
数学模型：在实验 3 中指出对应状态，并写出一个通过条件。
增长数量级：在实验 1 中指出对应状态，并写出一个通过条件。
设计更快算法：在实验 2 中指出对应状态，并写出一个通过条件。
内存使用：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“T(N) ≈ aN^b；doubling ratio ≈ 2^b；ThreeSum 暴力模型约为 N^3 / 6 次三元检查”不是孤立结论？

问题 3：故障恢复。 怎样证明“只取最快一次墙钟时间，或在扩大 N 时同时改变数据分布与实现版本”已经修复？

保存数据集哈希、N、基本操作计数、预热轮次、时间分布、拟合残差与输出校验作为正常基线；注入该故障并标记第一个违反“比较实现时必须固定输入分布、机器、JVM、预热、计数单位与正确性预言机”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Analysis of algorithms通过scientific method在observations与mathematical models间循环。
Doubling ratio消去coefficient，可由稳定ratio估计power-law exponent。
ThreeSum的sum tests是C(N,3)，leading term为N^3/6。
Order of growth用于scalability分类，不能替代constants、preconditions与实际measurements。
ThreeSumFast把growth降为N^2 log N，但当前官方实现要求distinct ints且忽略overflow。
Input dependence必须由明确distribution、structure或worst-case quantifier表达。
Memory usage要计objects、references、headers、alignment与capacity，并以目标runtime测量校验。