原书：《算法（第4版）》第1.4节 —— 算法分析
本文从 C++ 角度重新理解，配以详细中文说明、公式和代码示例。

一、Knuth 的核心洞察：程序运行时间由什么决定？

Donald Knuth 在计算机科学早期提出：任何程序的运行时间都可以用数学模型来描述。
他的基本思路是：
$$\text{总运行时间}=\sum _{\text{所有语句}}(\text{每条语句的执行次数}\times \text{每次执行的耗时})$$
这两个因素分别来自：

执行耗时   → 取决于硬件、编译器、操作系统（与程序无关）
执行次数   → 取决于程序逻辑和输入数据（这是分析的核心）

最难的部分就是确定每条语句的执行次数。

二、以 ThreeSum 为例（C++ 版）

ThreeSum 问题：给定 $N$ 个整数，统计其中三数之和为 0 的组合数。

C++ 完整代码

#include <iostream>
#include <vector>
#include <fstream>
// ——————————————————————————————————————————
// ThreeSum 暴力算法
// 三重循环枚举所有不同的三元组 (i, j, k)，检查是否三数和为 0
// 时间复杂度：O(N^3)
// ——————————————————————————————————————————
int threeSum(const std::vector<int>& a) {
    int N = (int)a.size();
    int cnt = 0;
    // 语句块 B：外层循环，执行 N 次
    for (int i = 0; i < N; i++) {
        // 语句块 C：中层循环，约执行 N^2/2 次
        for (int j = i + 1; j < N; j++) {
            // 语句块 D：内层循环，约执行 N^3/6 次
            // （三重循环中 i<j<k 的组合数，正好是从 N 个里取 3 个的方式数）
            for (int k = j + 1; k < N; k++) {
                // 语句块 E：条件判断，与 D 同频率，约 N^3/6 次
                // 每次判断访问 3 个数组元素（a[i]、a[j]、a[k]）
                if (a[i] + a[j] + a[k] == 0) {
                    cnt++;  // 语句块 E 内部：执行次数取决于输入，记为 x 次
                }
            }
        }
    }
    return cnt;
}
int main() {
    std::vector<int> a = {-5, -3, -2, 1, 2, 4, 6, -1};
    std::cout << "三数和为0的组合数: " << threeSum(a) << "\n";
    return 0;
}

各语句块的执行次数

语句块   执行次数
  A      1             （函数初始化，只跑一次）
  B      N             （外层循环 i 从 0 到 N-1）
  C      N^2/2 - N/2   （中层循环 j > i）
  D      N^3/6 - ...   （内层循环 k > j > i，即 C(N,3)）
  E      N^3/6 - ...   （if 判断，和 D 一样多次）
  cnt++  x             （取决于输入，0 到 N^3/6 都有可能）

精确的内层 if 执行次数是：
$$\frac{N(N-1)(N-2)}{6}=\frac{N^3}{6}-\frac{N^2}{2}+\frac{N}{3}$$
这就是从 $N$ 个数里选 3 个的组合数 $\left(\genfrac{}{}{0ex}{}{N}{3}\right)$。

三、波浪线近似（Tilde Approximation）

上面那个精确公式 $\frac{N^3}{6}-\frac{N^2}{2}+\frac{N}{3}$ 很繁琐。
当 $N$ 很大时，后面的项与 $\frac{N^3}{6}$ 相比微不足道。例如 $N=1000$：

N^3/6          = 166,666,667
N^2/2          =     500,000   （只有前者的 0.3%）
N/3            =         333   （可以完全忽略）

所以我们引入波浪线近似符号 $\sim$：

定义：如果 $g(N)/f(N)\to 1$（当 $N\to \infty$），就写作 $g(N)\sim f(N)$
直白理解：$g(N)$ 和 $f(N)$ 最终趋于相同，只保留最高次项。

常见近似例子

---

原始表达式	波浪线近似	增长阶数
$\frac{N^3}{6}-\frac{N^2}{2}+\frac{N}{3}$	$\sim \frac{N^3}{6}$	$N^3$
$\frac{N^2}{2}-\frac{N}{2}$	$\sim \frac{N^2}{2}$	$N^2$
$\lg N+1$	$\sim \lg N$	$\log N$
$3$	$\sim 3$	$1$（常数）

---

四、增长阶数（Order of Growth）

我们通常只关心函数的增长阶数，忽略前面的常数系数。
常见的增长阶数从小到大排列：

ASCII 增长速度对比（N = 1024 时的值）

增长阶数     N=1024 时的值        描述
---------   -----------------   ----------
1           1                   常数，最快
log N       10                  对数
N           1,024               线性
N log N     10,240              线性对数
N^2         1,048,576           平方
N^3         1,073,741,824       立方
2^N         无穷大（约10^308）   指数，最慢

增长阶数的直观理解

如果 N 翻倍（从 N 变成 2N），运行时间变成多少倍？
1       → 不变（常数）
log N   → 多加 1（对数增长极慢）
N       → 2 倍
N log N → 约 2 倍多一点
N^2     → 4 倍
N^3     → 8 倍
2^N     → 平方（指数爆炸！）

五、ThreeSum 的完整数学分析

设每个语句块执行一次的耗时为常数 $t_0,t_1,t_2,\dots$，总运行时间为：
$$T(N)=t_4\cdot 1+t_3\cdot N+t_2\cdot \left(\frac{N^2}{2}-\frac{N}{2}\right)+t_1\cdot \left(\frac{N^3}{6}-\frac{N^2}{2}+\frac{N}{3}\right)+t_0\cdot x$$
展开整理，按 $N$ 的幂次分组：
$$T(N)=\frac{t_1}{6}{N}^3+\left(\frac{t_2}{2}-\frac{t_1}{2}\right)N^2+\left(\frac{t_1}{3}-\frac{t_2}{2}+t_3\right)N+t_4+t_{0}x$$
当 $x$（三数和为 0 的组合数）较少时，波浪线近似为：
$$T(N)\sim \frac{t_1}{6}{N}^3$$
结论：ThreeSum 的增长阶数是 $N^3$。
这和实验结果一致（运行时间每次 $N$ 翻倍都增加约 8 倍）。

六、内层循环（Inner Loop）

Knuth 分析的一个关键观察：大多数程序的运行时间只取决于少数几条语句，这些语句就叫做内层循环。
对于 ThreeSum，内层循环是：

for (int k = j + 1; k < N; k++) {     // k 的递增和判断
    if (a[i] + a[j] + a[k] == 0) {    // 三数求和与判零
        cnt++;
    }
}

这部分执行了约 $N^3/6$ 次，远多于其他部分，它决定了整个程序的性能。

语句执行频率示意图：
频率
 |
 |                          *** D、E（~N^3/6）
 |                     ***
 |                ***
 |           ***             ** C（~N^2/2）
 |       ***
 |   ***
 |  * B（N）
 | * A（1）
 +-------------------------> N

七、成本模型（Cost Model）

为了把算法和具体实现（C++ 还是 Java、什么电脑）分开讨论，我们定义一个成本模型：指定一种"基本操作"作为计量单位。
对于 3-sum 问题，合适的成本模型是：数组访问次数（读或写都算一次）。
命题 B：暴力 3-sum 算法在 $N$ 个数中计算三数和为 0 的组合数，需要大约 $\frac{N^3}{2}$ 次数组访问。
证明：每个三元组访问 3 个元素，共有 $\sim \frac{N^3}{6}$ 个三元组，所以总访问次数为：
$$3\times \frac{N^3}{6}=\frac{N^3}{2}$$
成本模型的好处：

T(N) ~ a * N^3   中的 a 依赖于具体电脑（不同机器上 a 不同）
N^3              是算法本身的增长阶数（与电脑无关）
成本模型让我们只讨论 N^3，不用管 a 是多少。

八、验证：双倍测试（Doubling Test）

用实验来验证增长阶数是否真的是 $N^3$：每次把 $N$ 翻倍，记录运行时间，看时间是否变成约 8 倍（$2^3=8$）。

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cmath>
// ThreeSum（同上）
int threeSum(const std::vector<int>& a) {
    int N = (int)a.size();
    int cnt = 0;
    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)
                    cnt++;
    return cnt;
}
// ——————————————————————————————————————————
// 双倍测试：每次 N 翻倍，观察运行时间比值
// 如果比值趋近 8，说明增长阶数确实是 N^3
// ——————————————————————————————————————————
int main() {
    std::mt19937 rng(42);
    // 生成范围 [-M, M] 内的随机整数
    auto randInt = [&](int M) -> int {
        std::uniform_int_distribution<int> dist(-M, M);
        return dist(rng);
    };
    double prevTime = -1.0;
    std::cout << "   N       时间(ms)    比值(时间/上次时间)\n";
    std::cout << "------  -----------  --------------------\n";
    for (int N = 250; N <= 4000; N *= 2) {
        // 生成 N 个随机整数
        std::vector<int> a(N);
        for (int i = 0; i < N; i++) a[i] = randInt(1000000);
        // 计时
        auto start = std::chrono::high_resolution_clock::now();
        threeSum(a);
        auto end = std::chrono::high_resolution_clock::now();
        double ms = std::chrono::duration<double, std::milli>(end - start).count();
        double ratio = (prevTime > 0) ? ms / prevTime : 0.0;
        if (prevTime < 0)
            std::cout << " " << N << "      " << ms << "       (首次)\n";
        else
            std::cout << " " << N << "      " << ms << "       " << ratio << "\n";
        prevTime = ms;
    }
    return 0;
}

https://godbolt.org/z/8faeovano
预期输出规律：

   N       时间(ms)    比值
  250       ~0.5       （首次）
  500       ~4.0       ~8x
 1000       ~32        ~8x
 2000       ~256       ~8x
 4000       ~2048      ~8x
比值稳定在 8 左右，验证了增长阶数是 N^3。

九、属性 vs 命题

书中区分了两个概念：

概念	含义	例子
命题（Proposition）	关于算法的数学证明，基于成本模型，是严格的数学真理	命题B：暴力3-sum使用 $\sim N^3/2$ 次数组访问
属性（Property）	关于具体实现的假设，需要实验验证	属性A：ThreeSum 的运行时间增长阶数是 $N^3$

---

关系如下：

十、总结

程序运行时间分析的流程：
1. 找出所有语句块，分析执行次数
         ↓
2. 用波浪线近似，只保留最高次项
   g(N) = N^3/6 - N^2/2 + ...  →  ~N^3/6
         ↓
3. 确定增长阶数（忽略系数）
   ~N^3/6  →  增长阶数 N^3
         ↓
4. 定义成本模型，把算法和实现分开
   数组访问次数 ~N^3/2  →  命题 B
         ↓
5. 用双倍测试实验验证
   时间比值 → 8  →  印证 N^3

核心结论：ThreeSum 暴力算法的运行时间满足 $T(N)\sim a\cdot N^3$，其中 $a$ 是与机器相关的常数，增长阶数 $N^3$ 是算法本身的固有性质。

倍增比率实验（Doubling Ratio Experiments）

原文来自《算法》第4版 第1章第4节，以下内容从 C++ 角度重新理解和说明。

一、什么是倍增比率实验？

这是一种简单有效的方法，用来预测程序的运行时间，以及估算运行时间的增长量级。
基本步骤：

1. 准备一个能生成随机输入的函数（模拟真实场景的输入）
        |
        v
2. 每次把输入规模 N 翻倍，分别测量运行时间
        |
        v
3. 计算相邻两次运行时间的比值 ratio = T(2N) / T(N)
        |
        v
4. 当比值趋近于某个常数 2^b，实验结束
        |
        v
5. 结论：运行时间的增长量级约为 N^b

二、实验结果示例（ThreeSum 问题）

对 ThreeSum（找三个数之和为 0）做倍增比率实验，结果如下：

输入规模 N    运行时间(秒)    比值 T(2N)/T(N)
-----------  ------------   ---------------
      250         0.0            2.7
      500         0.0            4.8
     1000         0.1            6.9
     2000         0.8            7.7
     4000         6.4            8.0
     8000        51.1            8.0   <-- 比值稳定在 8
    16000       408.8            8.0   (预测)
    32000      3270.4            8.0   (预测)
    64000     26163.2            8.0   (预测)

比值稳定在 $8=2^3$，说明增长量级约为 $N^3$（立方阶），与 ThreeSum 暴力解一致。
预测方法：只需把上一次的运行时间乘以比值，即可预测下一次：
$$T(16000)\approx 51.1\times 8=408.8\text{ 秒}$$
$$T(32000)\approx 408.8\times 8=3270.4\text{ 秒}$$

三、为什么比值会趋近于常数？

命题 C（倍增比率定理）：
若运行时间满足 $T(N)\sim a{N}^b\lg N$，则：
$$\frac{T(2N)}{T(N)}\sim 2^b$$
推导过程：
$$\frac{T(2N)}{T(N)}=\frac{a\cdot (2N{)}^b\cdot \lg (2N)}{a\cdot N^b\cdot \lg N}$$
$$=2^b\cdot \frac{\lg (2N)}{\lg N}$$
$$=2^b\cdot \left(1+\frac{\lg 2}{\lg N}\right)$$
$$\stackrel{N\to \infty }{\to }{2}^b$$
当 $N$ 足够大时，$\frac{\lg 2}{\lg N}$ 趋近于 $0$，所以比值趋近于 $2^b$。

说人话：对数因子 $\lg N$ 对比值的影响随着 $N$ 增大而越来越小，最终可以忽略。这就是为什么即使是 $N\log N$ 的算法，其倍增比值也趋近于 $2^1=2$，而非更大的数。

四、C++ 完整实现

下面是 C++ 版本的倍增比率实验，以 ThreeSum 为例。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
// -------------------------------------------------------
// 生成 N 个范围在 [-range, range) 的随机整数
// -------------------------------------------------------
std::vector<int> generateRandom(int N, int range = 1000000) {
    std::vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        // 生成 [-range, range) 范围内的随机整数
        arr[i] = (std::rand() % (2 * range)) - range;
    }
    return arr;
}
// -------------------------------------------------------
// ThreeSum 暴力解：统计数组中和为 0 的三元组个数
// 时间复杂度 O(N^3)
// -------------------------------------------------------
int threeSum(const std::vector<int>& arr) {
    int N = static_cast<int>(arr.size());
    int cnt = 0;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            for (int k = j + 1; k < N; k++)
                if (arr[i] + arr[j] + arr[k] == 0)
                    cnt++;
    return cnt;
}
// -------------------------------------------------------
// 计时函数：生成 N 个随机整数，运行 threeSum，返回耗时（秒）
// -------------------------------------------------------
double timeTrial(int N) {
    auto arr = generateRandom(N);
    // 使用 C++ 高精度时钟计时
    auto start = std::chrono::high_resolution_clock::now();
    threeSum(arr);
    auto end   = std::chrono::high_resolution_clock::now();
    // 转换为秒（浮点数）
    std::chrono::duration<double> elapsed = end - start;
    return elapsed.count();
}
int main() {
    std::srand(42);  // 固定随机种子，保证结果可复现
    // 从 N=125 开始预热，得到第一个时间基准
    int startN = 125;
    double prev = timeTrial(startN);
    std::cout << "     N    时间(秒)    比值\n";
    std::cout << "------   --------   -----\n";
    // 每次将 N 翻倍，计算比值，直到手动终止
    // （实际使用时可以设定最大 N 或最大时间限制）
    for (int N = startN * 2; N <= 8000; N *= 2) {
        double time = timeTrial(N);
        // 比值 = 本次时间 / 上次时间，理想情况趋近于 2^b
        double ratio = (prev > 0.0) ? (time / prev) : 0.0;
        std::cout << std::fixed;
        std::cout.precision(1);
        std::cout << N << "\t" << time << "\t" << ratio << "\n";
        prev = time;  // 更新上一次时间
    }
    return 0;
}

https://godbolt.org/z/zrsbeM1ef
编译和运行：

g++ -O0 -o doubling_ratio doubling_ratio.cpp
./doubling_ratio

注意：使用 -O0 关闭编译器优化，避免优化干扰计时结果。
预期输出（大致）：

     N    时间(秒)    比值
------   --------   -----
250      0.0        ~3~5
500      0.0        ~5~7
1000     0.1        ~7
2000     0.8        ~8
4000     6.4        8.0
8000     51.1       8.0

比值稳定在 $8=2^3$ 后，即可判断增长量级为 $N^3$。

五、用比值预测运行时间

一旦比值 $r$ 稳定，预测公式非常简单：
$$T(2N)\approx r\times T(N)$$
对于更大倍数的预测（比如输入规模变为 $10N$）：
$$T(10N)\approx 10^b\times T(N)$$
其中 $b={\log }_{2}r$（即 $r=2^b$）。

示例计算

已知 ThreeSum 在 $N=8000$ 时耗时 $51.1$ 秒，$r=8$，则：

目标规模	计算过程	预测时间
$N=16000$	$51.1\times 8$	$408.8$ 秒
$N=32000$	$408.8\times 8$	$3270.4$ 秒
$N=64000$	$3270.4\times 8$	$26163.2$ 秒（约 7 小时）

---

六、各增长量级的倍增比值

---

增长量级	函数	倍增比值 $T(2N)/T(N)$
常数	$1$	$1$
对数	$\lg N$	$\approx 1$（极慢增长）
线性	$N$	$2$
线性对数	$N\lg N$	$\approx 2$
平方	$N^2$	$4$
立方	$N^3$	$8$
指数	$2^N$	$2^N$（无上限，不适用）

---

指数阶算法的比值没有上限，倍增实验对它无效。

七、实际应用：能不能在合理时间内处理大数据？

这是工程中最常见的问题：我的程序能处理这么大的数据吗？
根据增长量级，做一个量级估算（假设当前程序处理规模 $N$ 需要"几小时"）：

增长量级	函数	数据量变为 $10N$ 时	机器快 $10$ 倍时
线性	$N$	几小时	几小时
线性对数	$N\lg N$	几小时	几小时
平方	$N^2$	几天	一天
立方	$N^3$	几个月	几周
指数	$2^N$	永远不行	永远不行

---

结论：

• 线性或线性对数算法能跟上摩尔定律（计算机每 18 个月快 2 倍）的步伐。
• 平方和立方算法会被越来越大的数据量"压垮"，即使换更快的机器也追不上。
• 指数算法对于大规模输入完全不可行。

八、倍增比率实验流程（Mermaid）

九、ASCII 演示：比值收敛过程

倍增比率的收敛过程示意（ThreeSum, N^3）：
比值
  9 |
  8 |                    *----*----*----*   <- 稳定在 8 = 2^3
  7 |               *
  6 |          *
  5 |     *
  4 |  *
  3 |*
  2 |
  1 |
    +--+----+----+-----+-----+-----+------> N
      250  500  1000  2000  4000  8000
一开始比值不稳定（小 N 时误差大），随着 N 增大逐渐收敛。

十、关键结论总结

1. 倍增比率实验是一个快速实用的性能诊断工具。
只需几行代码，把输入规模翻倍并记录时间，就能判断程序的增长量级。
2. 比值趋近于 $2^b$，则增长量级为 $N^b$。

观测到的比值	对应增长量级
$\approx 2$	$N$ 或 $N\lg N$（线性或线性对数）
$\approx 4$	$N^2$（平方）
$\approx 8$	$N^3$（立方）

---

3. 实际建议：对每个性能敏感的程序都做一次倍增比率测试。
若比值为 $4$ 或 $8$，说明程序存在性能瓶颈，应当寻找更优算法。

性能分析的注意事项（Caveats）

原文来自《算法》第4版 第1章第4节，以下内容从 C++ 角度重新理解和说明。

总览

前面介绍的增长量级分析和倍增比率实验是强大的工具，但现实中存在一些因素会让实验结果不一致甚至产生误导。这些因素的本质是：我们建立数学模型时做了一些假设，而这些假设在某些情况下并不成立。

分析程序性能时的常见陷阱：
  大常数问题
  内层循环判断失误
  指令执行时间不均匀（缓存效应）
  系统环境干扰
  难以区分的两个程序
  结果对输入强依赖
  多个参数同时影响性能

下面逐一分析每种情况。

一、大常数问题（Large Constants）

我们通常只关注最高阶项，忽略低阶项的系数。但如果低阶项的系数非常大，这种近似就会失效。
例子：假设实际运行时间是：
$$T(N)=2N^2+cN$$
当 $c$ 很小时，用 $\sim 2N^2$ 近似完全没问题。
但如果 $c=10^3$ 或 $c=10^6$，在 $N$ 不够大的时候，$cN$ 这一项可能比 $2N^2$ 还要大，近似就会严重误导。
ASCII 演示：

T(N) = 2*N^2 + c*N，N 从小到大变化时各项的比较：
c = 10^6 的情况：
  N=100:    2*(100^2) = 20,000    vs   10^6*100 = 100,000,000  <- cN 远大于 2N^2!
  N=10^4:   2*(10^4)^2 = 2*10^8  vs   10^6*10^4 = 10^10       <- cN 仍然更大
  N=10^6:   2*10^12               vs   10^12                   <- 两项差不多
  N=10^8:   2*10^16               vs   10^14                   <- 2N^2 终于主导
结论：只有 N 足够大（远大于 c/2），最高阶项才真正主导。

教训：在 $N$ 较小时，不要盲目相信"量级分析"，要注意常数系数是否异常大。

二、内层循环判断失误（Nondominant Inner Loop）

我们假设"内层循环是最耗时的部分"，但这个假设有时不成立：

• 真正的"热点"代码可能被我们忽视了
• 当 $N$ 不够大时，高阶项还没来得及"主导"，低阶项的影响仍然明显
• 循环外有大量初始化或预处理代码，其开销不可忽视
  C++ 示例：一个容易判断失误的例子

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
// 这个函数看起来内层循环是 O(N^2)
// 但实际上排序 std::sort 的开销 O(N log N) 在 N 较小时也不可忽视
// 当 N 很小时，排序的常数系数可能比双层循环更显著
int countPairs(std::vector<int> arr) {
    int N = static_cast<int>(arr.size());
    // 预处理：排序，O(N log N)
    // 当 N 较小时，这里的常数开销可能超过下面的双层循环
    std::sort(arr.begin(), arr.end());
    int cnt = 0;
    // 内层循环：O(N^2)
    // 只有 N 足够大时，这里才是真正的瓶颈
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (arr[i] + arr[j] == 0)
                cnt++;
    return cnt;
}
int main() {
    // N 较小时，排序的开销占比较大；N 较大时，双层循环才主导
    for (int N : {10, 100, 1000}) {
        std::vector<int> arr(N);
        for (int i = 0; i < N; i++)
            arr[i] = (i % 7) - 3;  // 简单填充
        auto start = std::chrono::high_resolution_clock::now();
        countPairs(arr);
        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::micro> elapsed = end - start;
        std::cout << "N=" << N << " 耗时: " << elapsed.count() << " 微秒\n";
    }
    return 0;
}

代码深度解析：内层循环不一定是真正的瓶颈

一、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
int countPairs(std::vector<int> arr) {
    int N = static_cast<int>(arr.size());
    // 第一步：排序，时间复杂度 O(N log N)
    // 当 N 很小时，排序的"固定启动开销"可能比后面的循环更耗时
    std::sort(arr.begin(), arr.end());
    int cnt = 0;
    // 第二步：双层循环，时间复杂度 O(N^2)
    // 只有 N 足够大，这里才真正主导运行时间
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (arr[i] + arr[j] == 0)
                cnt++;
    return cnt;
}
int main() {
    for (int N : {10, 100, 1000}) {
        std::vector<int> arr(N);
        for (int i = 0; i < N; i++)
            arr[i] = (i % 7) - 3;  // 生成 -3,-2,-1,0,1,2,3 的循环序列
        auto start = std::chrono::high_resolution_clock::now();
        countPairs(arr);
        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::micro> elapsed = end - start;
        std::cout << "N=" << N << " 耗时: " << elapsed.count() << " 微秒\n";
    }
    return 0;
}

https://godbolt.org/z/avcqnz7P7

二、先搞清楚输入数据长什么样

main 里用这行填充数组：

arr[i] = (i % 7) - 3;

i % 7 的结果是 0,1,2,3,4,5,6 循环，减去 3 之后变成：

i:      0   1   2   3   4   5   6   7   8   9  10  11  12 ...
i%7:    0   1   2   3   4   5   6   0   1   2   3   4   5 ...
arr[i]: -3  -2  -1   0   1   2   3  -3  -2  -1   0   1   2 ...

整个数组是 -3,-2,-1,0,1,2,3 这七个值不断重复的循环序列。

三、countPairs 做了什么？

函数的目标是：统计数组中有多少对 (arr[i], arr[j]) 满足 arr[i] + arr[j] == 0，
即找所有互为相反数的数对。

执行流程

四、核心问题：谁才是真正的瓶颈？

这段代码里有两个部分，它们的理论复杂度不同：

部分	代码	时间复杂度
排序	std::sort(...)	$O(N\log N)$
双层循环	for i ... for j ...	$O(N^2)$

---

从纯粹的渐近分析来看，$N^2$ 增长比 $N\log N$ 快，所以双层循环是主导项。
但这是在 $N$ 足够大的前提下才成立。下面用具体数字来看。

五、用真实数字感受两部分的代价

操作次数的理论估算

设排序的每次比较代价为 $C_s$，双层循环每次比较代价为 $C_l$，则：

• 排序总代价约为：$C_s\cdot N{\log }_{2}N$
• 双层循环总代价约为：$C_l\cdot \frac{N(N-1)}{2}$
  在 $N$ 较小时，由于 $C_s$ 本身比较大（std::sort 内部有函数调用、模板实例化等固定开销），
  排序的绝对耗时可能超过双层循环。
  用数字估算（假设 $C_s=5$，$C_l=1$）：

---

N	排序代价 $5\cdot N{\log }_{2}N$	循环代价 $\frac{N(N-1)}{2}$	谁更大？
10	$5\times 33=165$	$45$	排序
50	$5\times 282=1410$	$1225$	排序
100	$5\times 664=3320$	$4950$	循环开始追上
1000	$5\times 9966=49830$	$499500$	循环完全主导
10000	$5\times 132877=664385$	$49995000$	循环远远主导

---

ASCII 图：两部分代价随 N 的变化

代价（相对单位）
    |
50M |                                          [循环]
    |                                        /
    |                                      /
10M |                                   /
    |                                /
 5M |                             /
    |                          /
 1M |                       /
    |              ________/______________ [排序]
500K|          ___/
    |       __/
100K|    __/
    |___/___________________________________________
    +--+----+-----+------+-------+---------> N
      10  100   500   1000   5000  10000
观察：
- N < ~50  时，排序代价 > 循环代价（排序是瓶颈）
- N ~ 50~100 时，两者接近（难以判断）
- N > ~100  时，循环代价快速超过排序（循环是瓶颈）

六、双层循环的执行过程（以 N=4 为例）

假设排序后数组为 [-2, -1, 1, 2]，看双层循环如何遍历所有数对：

下标:   0    1    2    3
数值:  -2   -1    1    2
i=0 (arr[0]=-2):
  j=1: -2 + (-1) = -3  不是0
  j=2: -2 +   1  = -1  不是0
  j=3: -2 +   2  =  0  -> cnt++ (**找到一对**)
i=1 (arr[1]=-1):
  j=2: -1 +   1  =  0  -> cnt++ (**找到一对**)
  j=3: -1 +   2  =  1  不是0
i=2 (arr[2]=1):
  j=3:  1 +   2  =  3  不是0
结果: cnt = 2

用表格展示所有检查的数对（上三角矩阵）：

       j=0   j=1   j=2   j=3
i=0  [skip]  -3    -1     0*
i=1  [skip] [skip]  0*    1
i=2  [skip] [skip] [skip]  3
i=3  [skip] [skip] [skip] [skip]
* 表示 sum==0，计数
总检查次数 = N*(N-1)/2 = 4*3/2 = 6 次

七、排序对循环有什么帮助？

你可能会问：既然排序不参与计数逻辑（循环里直接判断 arr[i]+arr[j]==0），为什么要排序？
这段代码里，排序其实没有被循环利用——双层循环仍然检查所有数对。排序在这里是多余的开销，这正是"代价模型选错"的体现：

本意：排序是为了后续可以用二分查找优化
实际：循环没有使用有序性，仍是暴力 O(N^2)
结果：白白多了一个 O(N log N) 的排序开销

如果真的要利用排序，应该改用二分查找替代内层循环（参考 TwoSumFast 的思路）：

优化思路：
  排序之后，对每个 arr[i]，
  用二分查找寻找 -arr[i] 是否在数组中，
  这样总复杂度从 O(N^2) 降低到 O(N log N)

八、计时代码的工作原理

auto start = std::chrono::high_resolution_clock::now();  // 记录开始时间点
countPairs(arr);                                          // 运行被测函数
auto end   = std::chrono::high_resolution_clock::now();  // 记录结束时间点
// duration<double, std::micro> 把时间差转换为"微秒"单位的浮点数
std::chrono::duration<double, std::micro> elapsed = end - start;
std::cout << elapsed.count() << " 微秒\n";

时间单位换算：

1 秒 = 1,000 毫秒 (ms)
1 毫秒 = 1,000 微秒 (us)
1 微秒 = 1,000 纳秒 (ns)
std::micro -> 微秒
std::milli -> 毫秒
std::nano  -> 纳秒

九、完整执行流程总览

十、关键结论

1. 双层循环是名义上的"内层循环"，理论上是 O(N^2) 主导项
   但在 N 较小时，O(N log N) 的排序因常数系数大反而更耗时
2. 判断谁是真正瓶颈，不能只看渐近复杂度，还要看：
   - N 的实际大小
   - 每部分操作的常数系数
3. 这个函数的排序实际上是多余的：
   循环没有利用有序性，相当于白花了 O(N log N) 的代价
4. 要真正利用排序来加速，需要配合二分查找，
   才能把总复杂度从 O(N^2) 降到 O(N log N)

三、指令执行时间不均匀——缓存效应（Instruction Time / Caching）

现代计算机使用**多级缓存（Cache）**来加速内存访问。访问"靠近"的内存地址比访问"分散"的地址快得多。
缓存层级示意（ASCII）：

访问速度（从快到慢）：
  CPU 寄存器    ~1 个时钟周期
      |
  L1 Cache     ~4 个时钟周期    容量: ~32 KB
      |
  L2 Cache     ~12 个时钟周期   容量: ~256 KB
      |
  L3 Cache     ~40 个时钟周期   容量: ~8 MB
      |
  主内存(RAM)  ~200 个时钟周期  容量: GB 级别
      |
  硬盘/SSD     ~百万个时钟周期
当数组很大，数据无法放入缓存时，访问速度会急剧下降！

对倍增实验的影响：ThreeSum 在小数组上比值稳定在 $8$，但当数组大到超出缓存容量时，大量缓存未命中（cache miss）会导致：
$$\text{实测比值}>8$$
这看起来像是算法变慢了，其实是缓存效应在作怪，而非算法本身的增长量级变了。
C++ 示例：顺序访问 vs 跳跃访问的速度差异

#include <iostream>
#include <vector>
#include <chrono>
// 顺序访问数组（缓存友好）
long long sequentialAccess(const std::vector<int>& arr) {
    long long sum = 0;
    int N = static_cast<int>(arr.size());
    // 连续地址访问，缓存命中率高
    for (int i = 0; i < N; i++)
        sum += arr[i];
    return sum;
}
// 跳跃访问数组（缓存不友好）
long long stridedAccess(const std::vector<int>& arr, int stride) {
    long long sum = 0;
    int N = static_cast<int>(arr.size());
    // 每隔 stride 个元素访问一次，缓存命中率低
    for (int i = 0; i < N; i += stride)
        sum += arr[i];
    return sum;
}
int main() {
    const int N = 64 * 1024 * 1024;  // 64M 个整数，约 256 MB，超出 L3 缓存
    std::vector<int> arr(N, 1);
    // 测试顺序访问
    auto t1 = std::chrono::high_resolution_clock::now();
    long long s1 = sequentialAccess(arr);
    auto t2 = std::chrono::high_resolution_clock::now();
    // 测试跳跃访问（步长=16，实际访问元素数相同量级）
    auto t3 = std::chrono::high_resolution_clock::now();
    long long s2 = stridedAccess(arr, 1);  // 步长1，做对比基准
    auto t4 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> seq_time  = t2 - t1;
    std::chrono::duration<double> strd_time = t4 - t3;
    std::cout << "顺序访问耗时: " << seq_time.count()  << " 秒 (sum=" << s1 << ")\n";
    std::cout << "步长1访问耗时: " << strd_time.count() << " 秒 (sum=" << s2 << ")\n";
    std::cout << "（对大数组尝试更大步长可观察缓存效应）\n";
    return 0;
}

https://godbolt.org/z/xvqnjzbPP

四、系统环境干扰（System Considerations）

即使算法本身不变，操作系统层面的各种活动都会影响计时结果：

干扰来源	说明
操作系统调度	CPU 时间片被其他进程抢占
垃圾回收	Java 有 GC，C++ 中频繁 new/delete 也有开销
JIT 编译	Java 特有；C++ 没有，但动态链接库加载也有开销
后台下载/更新	占用内存带宽，影响缓存效率
CPU 频率动态调节	现代 CPU 会根据温度和负载动态调整主频（睿频）

---

核心问题：实验的可重复性受到威胁。同一段代码，每次运行的计时结果可能都不完全相同。
C++ 应对建议：

#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>
// 多次运行取中位数，减少偶发性系统干扰的影响
double medianTime(int N, int trials = 5) {
    std::vector<double> times(trials);
    for (int t = 0; t < trials; t++) {
        // 准备输入
        std::vector<int> arr(N);
        for (int i = 0; i < N; i++)
            arr[i] = i - N / 2;
        // 计时
        auto start = std::chrono::high_resolution_clock::now();
        // 被测逻辑（这里用简单求和代替）
        long long sum = 0;
        for (int x : arr) sum += x;
        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed = end - start;
        times[t] = elapsed.count();
        (void)sum;  // 防止编译器优化掉计算
    }
    // 取中位数（排序后取中间值）
    std::sort(times.begin(), times.end());
    return times[trials / 2];
}
int main() {
    for (int N : {100000, 200000, 400000}) {
        double t = medianTime(N);
        std::cout << "N=" << N << " 中位耗时: " << t << " 秒\n";
    }
    return 0;
}

五、难以区分的两个程序（Too Close to Call）

有时候两个算法的性能非常接近，在不同输入或不同机器上互有胜负。这时候不要执着于找"绝对的最快"，因为：

• 各种常数系数和缓存效应可能逆转结果
• 输入的分布可能改变胜负
• 不同 CPU 架构的指令集优化不同
  建议：除非差距非常显著（超过 2 倍），否则优先考虑代码可读性和可维护性，而不是微优化。

六、结果对输入强依赖（Strong Dependence on Inputs）

很多算法的运行时间不是固定的，而是强烈依赖于输入内容。
C++ 示例：将 ThreeSum 改为"找到第一个就返回"

#include <iostream>
#include <vector>
// 原版：统计所有三元组，必须遍历所有情况，始终是 O(N^3)
int threeSumCount(const std::vector<int>& arr) {
    int N = static_cast<int>(arr.size());
    int cnt = 0;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            for (int k = j + 1; k < N; k++)
                if (arr[i] + arr[j] + arr[k] == 0)
                    cnt++;
    return cnt;
}
// 改版：找到一个就返回 true，找不到返回 false
// 最好情况：O(1)（前三个数就满足）
// 最坏情况：O(N^3)（没有满足条件的三元组）
bool threeSumExists(const std::vector<int>& arr) {
    int N = static_cast<int>(arr.size());
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            for (int k = j + 1; k < N; k++)
                if (arr[i] + arr[j] + arr[k] == 0)
                    return true;   // 找到立刻返回！
    return false;
}
int main() {
    // 情况1：第一个三元组就满足条件 -> 接近 O(1)
    std::vector<int> easyCase = {-1, 0, 1, 5, 7, 9};
    std::cout << "存在三元组(简单输入): "
              << (threeSumExists(easyCase) ? "是" : "否") << "\n";
    // 情况2：没有满足条件的三元组 -> O(N^3)
    std::vector<int> hardCase = {1, 2, 4, 8, 16, 32};
    std::cout << "存在三元组(困难输入): "
              << (threeSumExists(hardCase) ? "是" : "否") << "\n";
    return 0;
}

增长量级分析：

输入情况	增长量级
前三个数就满足 $a+b+c=0$	$O(1)$（常数）
存在满足条件的三元组（中间位置）	$O(N^2)$ 到 $O(N^3)$ 之间
不存在任何满足条件的三元组	$O(N^3)$（立方）

---

这说明对于"提前退出"的算法，倍增比率实验的结果会因输入而异，无法得到稳定的比值。

七、多个参数同时影响性能（Multiple Problem Parameters）

很多算法的性能不是由单一参数 $N$ 决定的，而是由多个参数共同决定。
典型例子：白名单过滤（Whitelist）

• 白名单大小：$N$
• 标准输入数量：$M$（且 $M\gg N$）
• 实际运行时间：$\sim M\log N$
  这里有两个独立参数 $M$ 和 $N$，如果只对 $N$ 做倍增实验而保持 $M$ 不变，得到的结论可能完全错误。
  Mermaid 图：多参数性能依赖关系

C++ 示例：两个参数的情况

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
// 在有序白名单中二分查找 key
bool inWhitelist(const std::vector<int>& whitelist, int key) {
    int lo = 0, hi = static_cast<int>(whitelist.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if      (key < whitelist[mid]) hi = mid - 1;
        else if (key > whitelist[mid]) lo = mid + 1;
        else                           return true;
    }
    return false;
}
// 白名单过滤：统计 input 中有多少数不在 whitelist 里
// 时间复杂度 O(M log N)，M = input.size()，N = whitelist.size()
int whitelistFilter(const std::vector<int>& whitelist,
                    const std::vector<int>& input) {
    int cnt = 0;
    for (int x : input)
        if (!inWhitelist(whitelist, x))
            cnt++;
    return cnt;
}
int main() {
    // 演示：固定 N，改变 M，观察运行时间与 M 的关系（应近似线性）
    std::vector<int> whitelist(1000);
    for (int i = 0; i < 1000; i++) whitelist[i] = i * 2;  // 偶数白名单
    for (int M : {10000, 20000, 40000, 80000}) {
        std::vector<int> input(M);
        for (int i = 0; i < M; i++) input[i] = i % 3000;
        auto start = std::chrono::high_resolution_clock::now();
        int result = whitelistFilter(whitelist, input);
        auto end   = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::micro> elapsed = end - start;
        std::cout << "M=" << M << " N=1000 "
                  << "不在白名单的数: " << result
                  << " 耗时: " << elapsed.count() << " 微秒\n";
    }
    return 0;
}

https://godbolt.org/z/rnr1zf8qT
运行时间随 $M$ 线性增长（每次翻倍，时间约翻倍），因为 $N$ 固定时 $\log N$ 是常数。

八、总结：注意事项一览

九、核心观点

尽管存在上述诸多注意事项，理解程序运行时间的增长量级仍然是每个程序员最重要的性能知识。
用一个类比来说：

• 火箭科学家需要知道测试飞行会落在海洋里还是城市里——不需要精确到米，但必须知道量级。
• 医学研究者需要知道药物试验会治愈还是杀死受试者——不需要精确概率，但方向不能错。
• 程序员需要知道程序运行需要一秒还是一年——不需要精确到毫秒，但量级不能算错。
  掌握增长量级分析，就是掌握了程序性能的"方向感"。

应对输入依赖的四种方法

原文来自《算法》第4版 第1章第4节，以下内容从 C++ 角度重新理解和说明。

一、为什么输入依赖是个大问题？

上一节提到，程序的运行时间有时严重依赖输入内容。以修改版 ThreeSum 为例：

• 最好情况：前三个数之和就是 $0$，直接返回，运行时间为 $O(1)$
• 最坏情况：没有任何满足条件的三元组，运行时间为 $O(N^3)$
  同一段代码，运行时间从常数到立方，差距极大。针对这个问题，有四种常见的应对策略。

二、方法一：建立输入模型（Input Models）

思路：对程序实际会处理的输入，建立一个合理的数学模型，然后基于这个模型来分析性能。
例子：假设 ThreeSum 的输入是随机的 int 整数，那么可以用概率方法分析"恰好有三个数之和为零"的期望次数，从而得出期望运行时间。
两个挑战：

1. 模型可能不现实：真实输入往往有规律，不是纯随机的。比如分析基因组数据的程序，"随机碱基序列"根本不符合真实基因组的特征，用随机模型预测出来的性能可能完全错误。
2. 分析可能极度复杂：即使模型合理，数学推导也可能超出普通程序员的能力范围。
   结论：输入模型方法适合配合经典数学分析使用，本书会在具体算法处介绍典型案例。

三、方法二：最坏情况保证（Worst-Case Performance Guarantees）

思路：不管输入是什么，运行时间都不超过某个上界。
什么时候必须用最坏情况分析？
某些系统对延迟有严格要求，一次超时就可能造成灾难：

核反应堆控制软件    -> 超时可能导致灾难
心脏起搏器固件      -> 超时可能危及生命
汽车制动系统        -> 超时可能导致事故

还有一个容易被忽视的场景：拒绝服务攻击（DoS Attack）。黑客可以精心构造"最坏输入"来拖垮服务器，如果算法没有最坏情况保证，就会被这种攻击击溃。
命题 D：链表实现的 Bag、Stack、Queue，所有操作在最坏情况下都是常数时间。
下面用 C++ 实现一个链表栈，并验证每次操作确实是 $O(1)$：

#include <iostream>
#include <stdexcept>
// 链表节点
// 每次 push/pop 只操作链表头节点，无论栈有多大，都是常数时间
template<typename T>
struct Node {
    T     val;    // 存储的值
    Node* next;   // 指向下一个节点
    Node(T v, Node* n) : val(v), next(n) {}
};
// 链表栈：所有操作均为 O(1) 最坏情况
template<typename T>
class LinkedStack {
    Node<T>* head;  // 栈顶指针
    int      sz;    // 当前元素个数
public:
    LinkedStack() : head(nullptr), sz(0) {}
    ~LinkedStack() {
        // 析构时逐个释放节点
        while (head) {
            Node<T>* tmp = head;
            head = head->next;
            delete tmp;
        }
    }
    // O(1): 在链表头部插入新节点
    void push(T val) {
        head = new Node<T>(val, head);
        sz++;
    }
    // O(1): 移除并返回链表头节点
    T pop() {
        if (sz == 0) throw std::underflow_error("Stack is empty");
        T    result = head->val;
        Node<T>* tmp = head;
        head = head->next;
        delete tmp;
        sz--;
        return result;
    }
    bool empty() const { return sz == 0; }
    int  size()  const { return sz; }
};
int main() {
    LinkedStack<int> stk;
    // 无论压入多少元素，每次 push/pop 都只操作头节点
    // 指令数有固定上界，与栈的大小无关 -> O(1) 最坏情况
    for (int i = 0; i < 5; i++)
        stk.push(i * 10);
    while (!stk.empty())
        std::cout << stk.pop() << " ";   // 输出: 40 30 20 10 0
    std::cout << "\n";
    return 0;
}

https://godbolt.org/z/1nG3Kn9KK

代码深度解析：链表栈与 O(1) 最坏情况保证

一、这段代码要解决什么问题？

栈（Stack）是一种"后进先出"的数据结构，就像一叠盘子：

最后放上去的盘子，第一个被取走
    +---------+
    |  盘子4  |  <- 最后放，第一个取（栈顶）
    +---------+
    |  盘子3  |
    +---------+
    |  盘子2  |
    +---------+
    |  盘子1  |  <- 最先放，最后取（栈底）
    +---------+

栈有两种常见实现方式：

实现方式	push/pop 时间	缺点
动态数组	均摊 $O(1)$，偶尔扩容需 $O(N)$	有时会出现一次很慢的操作
链表	每次严格 $O(1)$	每个节点有额外的指针开销

---

这段代码选择链表实现，目的是保证每次操作都严格是常数时间，没有任何例外情况。

二、核心数据结构：链表节点

template<typename T>
struct Node {
    T     val;    // 存储的值
    Node* next;   // 指向下一个节点（如果是最后一个节点，next = nullptr）
    Node(T v, Node* n) : val(v), next(n) {}
};

一个节点就像一个小盒子，里面装着：

• val：真正要存储的数据
• next：一根"绳子"，指向下一个盒子
  多个节点串在一起就形成链表：

head
 |
 v
[val=40 | next]-->[val=30 | next]-->[val=20 | next]-->[val=10 | next]-->[val=0 | next=nullptr]

三、LinkedStack 的内部结构

template<typename T>
class LinkedStack {
    Node<T>* head;  // 永远指向第一个节点（栈顶）
    int      sz;    // 记录当前有多少个元素
    ...
};

head 是整个栈的"入口"，所有操作都从这里开始。sz 只是一个计数器，方便快速查询栈的大小。

四、push 操作详解

void push(T val) {
    head = new Node<T>(val, head);  // 创建新节点，让它的 next 指向原来的 head
    sz++;                            // 元素数量 +1
}

关键理解：new Node<T>(val, head) 这一行同时做了两件事：

1. 创建一个新节点，值为 val
2. 把新节点的 next 设置为原来的 head（即把新节点接到原链表前面）
   然后 head 更新为这个新节点，新节点就成了新的栈顶。

push 的过程演示（依次 push 0, 10, 20）

初始状态（空栈）：

head = nullptr
sz = 0

push(0)：

创建节点：[val=0 | next=nullptr]
head 指向它
head
 |
 v
[val=0 | next=nullptr]
sz = 1

push(10)：

创建节点：[val=10 | next = 原来的head]
head 更新为新节点
head
 |
 v
[val=10 | next]-->[val=0 | next=nullptr]
sz = 2

push(20)：

head
 |
 v
[val=20 | next]-->[val=10 | next]-->[val=0 | next=nullptr]
sz = 3

规律：每次新元素都插在链表最前面，操作只涉及 head 指针，与链表长度完全无关，所以是 $O(1)$。

五、pop 操作详解

T pop() {
    if (sz == 0) throw std::underflow_error("Stack is empty");
    T        result = head->val;   // 保存栈顶的值，准备返回
    Node<T>* tmp    = head;        // 用 tmp 记住要删除的节点
    head = head->next;             // head 向后移动一步
    delete tmp;                    // 释放原来的栈顶节点
    sz--;
    return result;
}

pop 的过程演示

当前状态：

head
 |
 v
[val=20 | next]-->[val=10 | next]-->[val=0 | next=nullptr]

第一步：保存栈顶值，result = 20
第二步：tmp 指向当前栈顶节点

head tmp（将要被删除）
 |   |
 v   v
[val=20 | next]-->[val=10 | next]-->[val=0 | next=nullptr]
（此时 head 和 tmp 指向同一个节点）

第三步：head = head->next，head 向后移

tmp（将要被删除）
 |
 v
[val=20 | next]-->[val=10 | next]-->[val=0 | next=nullptr]
                   ^
                   |
                  head（移到这里了）

第四步：delete tmp，释放原栈顶节点

head
 |
 v
[val=10 | next]-->[val=0 | next=nullptr]
sz = 2，返回 result = 20

规律：pop 只操作 head 指针和第一个节点，同样与链表长度无关，严格 $O(1)$。

六、析构函数：清理所有节点

~LinkedStack() {
    while (head) {
        Node<T>* tmp = head;
        head = head->next;
        delete tmp;
    }
}

析构函数就是把 pop 的过程重复做，直到链表为空，把每个节点都 delete 掉，防止内存泄漏。

初始链表：
head -> [20] -> [10] -> [0] -> nullptr
第1次循环：delete [20]，head 移到 [10]
第2次循环：delete [10]，head 移到 [0]
第3次循环：delete [0]，head 变成 nullptr
循环结束

七、main 函数的完整执行过程

for (int i = 0; i < 5; i++)
    stk.push(i * 10);       // 依次 push: 0, 10, 20, 30, 40
while (!stk.empty())
    std::cout << stk.pop(); // 依次 pop: 40, 30, 20, 10, 0

push 阶段（链表状态变化）

push(0):   head->[0]->nullptr
push(10):  head->[10]->[0]->nullptr
push(20):  head->[20]->[10]->[0]->nullptr
push(30):  head->[30]->[20]->[10]->[0]->nullptr
push(40):  head->[40]->[30]->[20]->[10]->[0]->nullptr

pop 阶段（输出顺序）

pop() 返回 40:  head->[30]->[20]->[10]->[0]->nullptr
pop() 返回 30:  head->[20]->[10]->[0]->nullptr
pop() 返回 20:  head->[10]->[0]->nullptr
pop() 返回 10:  head->[0]->nullptr
pop() 返回  0:  head->nullptr（栈空）
屏幕输出：40 30 20 10 0

后进先出的本质：最后 push 的 40 在链表最前面，最先被 pop 出来。

八、为什么每次操作都是严格 O(1)？

用一张表对比每个操作真正执行了哪些固定步骤：

操作	实际执行的步骤	步骤数量
push(val)	new 一个节点、设置 next、更新 head、sz++	固定 4 步
pop()	读 head->val、保存 tmp、移动 head、delete、sz–	固定 5 步
empty()	比较 sz == 0	固定 1 步
size()	返回 sz	固定 1 步

---

无论栈里有 1 个元素还是 100 万个元素，步骤数量完全一样，这就是 $O(1)$ 最坏情况的保证。

九、整体流程图

十、push 和 pop 的操作细节（Mermaid）

十一、模板（template）的作用

template<typename T>
class LinkedStack { ... };

template<typename T> 意思是：T 是一个"占位符类型"，实际使用时再指定。

LinkedStack<int>    stk1;   // T = int,    存整数
LinkedStack<double> stk2;   // T = double, 存浮点数
LinkedStack<std::string> stk3; // T = string, 存字符串

同一套代码，适用于任意数据类型，不需要为每种类型单独写一遍。

十二、关键结论

1. 链表栈的每个操作只涉及头节点
   push: 在链表头部插入一个新节点
   pop:  把头节点取出并释放
   无论链表有多长，步骤数固定 -> 严格 O(1) 最坏情况
2. 后进先出（LIFO）的实现原理
   push 总是插在链表最前面
   pop 总是从链表最前面取
   所以最后 push 的元素第一个被 pop
3. 析构函数必须手动释放所有节点
   C++ 不像 Java 有垃圾回收，每个 new 必须对应一个 delete
   忘记析构会导致内存泄漏
4. 与动态数组栈的区别
   链表栈：每次操作严格 O(1)，无例外
   数组栈：大多数操作 O(1)，偶尔扩容需要 O(N)（但均摊后仍是 O(1)）
   若系统对单次操作延迟有严格要求（如心脏起搏器），必须用链表栈

四、方法三：随机化算法（Randomized Algorithms）

思路：在算法中主动引入随机性，使得"最坏情况"发生的概率极低，从而提供概率意义上的性能保证。

快速排序（Quicksort）

• 不随机化时：最坏情况（如已排序数组）退化为 $O(N^2)$
• 随机打乱输入后：以极高概率保证 $O(N\log N)$，退化的概率比计算机被雷击还低

#include <iostream>
#include <vector>
#include <algorithm>   // std::shuffle
#include <random>      // std::mt19937, std::random_device
// 分区函数：把 arr[lo..hi] 以 arr[lo] 为基准分成两部分
// 返回基准元素的最终位置
int partition(std::vector<int>& arr, int lo, int hi) {
    int pivot = arr[lo];   // 选第一个元素为基准
    int i = lo + 1;
    int j = hi;
    while (true) {
        while (i <= hi && arr[i] < pivot) i++;  // 从左找第一个 >= pivot 的
        while (j > lo  && arr[j] > pivot) j--;  // 从右找第一个 <= pivot 的
        if (i >= j) break;
        std::swap(arr[i], arr[j]);
    }
    std::swap(arr[lo], arr[j]);   // 把基准放到正确位置
    return j;
}
// 随机化快速排序
// 关键：排序前先随机打乱，保证任何输入的期望时间都是 O(N log N)
// 不打乱的话，已排序输入会导致 O(N^2)
void quickSort(std::vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}
int main() {
    std::vector<int> arr = {5, 3, 8, 1, 9, 2, 7, 4, 6};
    // 排序前随机打乱，消除最坏情况
    std::mt19937 rng(std::random_device{}());
    std::shuffle(arr.begin(), arr.end(), rng);
    quickSort(arr, 0, static_cast<int>(arr.size()) - 1);
    for (int x : arr) std::cout << x << " ";   // 输出: 1 2 3 4 5 6 7 8 9
    std::cout << "\n";
    return 0;
}

代码深度解析：随机化快速排序

一、整体思路：分而治之

快速排序的核心思想是分治：每次从数组里挑一个"基准"（pivot），
把所有比它小的放左边，比它大的放右边，然后对左右两部分递归做同样的事。

原数组：[5, 3, 8, 1, 9, 2, 7, 4, 6]
选基准 5，分区后：
  左边（< 5）: [3, 1, 2, 4]
  基准位置:    [5]
  右边（> 5）: [8, 9, 7, 6]
再对左边和右边分别重复，最终合并结果就是有序数组

整个过程不需要额外的合并步骤（与归并排序不同），分区完成后位置就已经是最终位置了。

二、partition 函数：最关键的一步

int partition(std::vector<int>& arr, int lo, int hi) {
    int pivot = arr[lo];   // 选最左边的元素作为基准
    int i = lo + 1;        // 左指针，从基准右边出发
    int j = hi;            // 右指针，从最右边出发
    while (true) {
        while (i <= hi && arr[i] < pivot) i++;  // i 向右走，直到遇到 >= pivot 的
        while (j > lo  && arr[j] > pivot) j--;  // j 向左走，直到遇到 <= pivot 的
        if (i >= j) break;                       // 两指针相遇或交叉，停止
        std::swap(arr[i], arr[j]);               // 交换两个"放错边"的元素
    }
    std::swap(arr[lo], arr[j]);  // 把基准放到最终位置（j 的位置）
    return j;                    // 返回基准的最终下标
}

两个指针各自的任务

i 从左往右扫：寻找"不该在左边"的元素（即 >= pivot 的）
j 从右往左扫：寻找"不该在右边"的元素（即 <= pivot 的）
找到之后互换，让它们各回各位

三、partition 手动演示

用数组 [5, 3, 8, 1, 9, 2, 7, 4, 6]，lo=0, hi=8，pivot = arr[0] = 5。

初始状态

下标:  0   1   2   3   4   5   6   7   8
数组: [5,  3,  8,  1,  9,  2,  7,  4,  6]
       ^                                ^
      pivot=5                          j=8
       i=1（从 lo+1 出发）

第一轮循环

i 向右找第一个 >= 5 的：
  arr[1]=3 < 5, i++  -> i=2
  arr[2]=8 >= 5, 停  -> i=2
j 向左找第一个 <= 5 的：
  arr[8]=6 > 5, j--  -> j=7
  arr[7]=4 <= 5, 停  -> j=7
i=2 < j=7，交换 arr[2] 和 arr[7]：

下标:  0   1   2   3   4   5   6   7   8
数组: [5,  3,  4,  1,  9,  2,  7,  8,  6]
                ^                   ^
               i=2                 j=7（交换后）

第二轮循环

i 继续右移（从 i=2 重新开始，因为刚换过来的 arr[2]=4 < 5）：
  arr[2]=4 < 5, i++  -> i=3
  arr[3]=1 < 5, i++  -> i=4
  arr[4]=9 >= 5, 停  -> i=4
j 继续左移（从 j=7 重新开始）：
  arr[7]=8 > 5, j--  -> j=6
  arr[6]=7 > 5, j--  -> j=5
  arr[5]=2 <= 5, 停  -> j=5
i=4 < j=5，交换 arr[4] 和 arr[5]：

下标:  0   1   2   3   4   5   6   7   8
数组: [5,  3,  4,  1,  2,  9,  7,  8,  6]
                        ^   ^
                       i=4 j=5（交换后）

第三轮循环

i 继续右移：
  arr[4]=2 < 5, i++  -> i=5
  arr[5]=9 >= 5, 停  -> i=5
j 继续左移：
  arr[5]=9 > 5, j--  -> j=4
  arr[4]=2 <= 5, 停  -> j=4
i=5 > j=4，i >= j，跳出循环

收尾：把 pivot 放到正确位置

交换 arr[lo]=arr[0] 和 arr[j]=arr[4]：
下标:  0   1   2   3   4   5   6   7   8
数组: [2,  3,  4,  1,  5,  9,  7,  8,  6]
                        ^
                      pivot=5 的最终位置，下标 j=4

验证分区结果

下标:  0   1   2   3  |4|  5   6   7   8
数组: [2,  3,  4,  1, |5|  9,  7,  8,  6]
      <----- 全 < 5 ---->  <--- 全 > 5 --->
左边 [2,3,4,1]  全部 < 5   正确
基准 [5]        在下标 4    正确
右边 [9,7,8,6]  全部 > 5   正确

四、partition 流程图

五、quickSort 递归过程

void quickSort(std::vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;            // 只有 0 或 1 个元素，不需要排序
    int p = partition(arr, lo, hi);  // 分区，p 是基准的最终位置
    quickSort(arr, lo, p - 1);       // 递归排序左半部分
    quickSort(arr, p + 1, hi);       // 递归排序右半部分
}

递归的终止条件：lo >= hi，即区间内只剩 0 个或 1 个元素，已经"有序"了，直接返回。

六、完整递归树（以小数组为例）

用 [3, 1, 4, 2] 演示完整递归过程：

七、为什么要在排序前随机打乱？

不打乱的最坏情况

如果输入已经是有序数组 [1, 2, 3, 4, 5]，每次选最左边作为 pivot：

第1次 partition: pivot=1，左边空，右边 [2,3,4,5]
第2次 partition: pivot=2，左边空，右边 [3,4,5]
第3次 partition: pivot=3，左边空，右边 [4,5]
...

递归树退化成一条直线：

[1, 2, 3, 4, 5]
      |
  pivot=1，右边 [2,3,4,5]
      |
  pivot=2，右边 [3,4,5]
      |
  pivot=3，右边 [4,5]
      |
  pivot=4，右边 [5]
      |
   返回
深度 = N，每层工作量 = O(N)，总计 O(N^2)

打乱后的理想情况

每次 pivot 恰好落在中间，递归树是平衡的：

深度约 log N 层，每层总工作量 O(N)
总计 O(N log N)

ASCII 对比图

不打乱（已排序输入）：       打乱后（随机输入）：
退化为链状，深度 N            平衡二叉树，深度 log N
     [1..5]                      [1..5]
       |                        /      \
     [2..5]                 [1..2]    [4..5]
       |                    /    \    /    \
     [3..5]               [1]  [2] [4]  [5]
       |
     [4..5]
       |
      [5]
每层 O(N) 工作量           每层 O(N) 工作量
共 N 层                    共 log N 层
总计 O(N^2)                总计 O(N log N)

随机打乱的代码

std::mt19937 rng(std::random_device{}());
std::shuffle(arr.begin(), arr.end(), rng);

• std::random_device{}() 从硬件取一个真随机种子（熵源）
• std::mt19937 是梅森旋转算法，一种高质量伪随机数生成器
• std::shuffle 用 Fisher-Yates 算法把数组均匀随机打乱
  打乱后，不管原始输入是什么（有序、逆序、全相同），都变成了随机排列，
  极大概率让每次 partition 选到"中等大小"的 pivot，从而保证 $O(N\log N)$ 的期望时间。

八、main 函数完整流程

九、用大数组的一次 partition 再感受一遍（ASCII）

数组 [5, 3, 8, 1, 9, 2, 7, 4, 6] 在 partition 过程中，指针移动示意：

初始：
  pivot = 5（下标 0）
  i = 1（->）   j = 8（<-）
  下标: 0   1   2   3   4   5   6   7   8
       [5,  3,  8,  1,  9,  2,  7,  4,  6]
            i->                        <-j
i 向右找 >=5：跳过3，停在8（下标2）
j 向左找 <=5：跳过6，停在4（下标7）
  i=2 < j=7，交换 arr[2] 和 arr[7]：
  下标: 0   1   2   3   4   5   6   7   8
       [5,  3,  4,  1,  9,  2,  7,  8,  6]
                i->              <-j
i 继续右移，跳过4、1，停在9（下标4）
j 继续左移，跳过7、8、9，停在2（下标5）
  i=4 < j=5，交换 arr[4] 和 arr[5]：
  下标: 0   1   2   3   4   5   6   7   8
       [5,  3,  4,  1,  2,  9,  7,  8,  6]
                        i-> <-j
i 继续右移，跳过2，停在9（下标5）
j 继续左移，9>5 跳过，停在2（下标4）
  i=5 > j=4，两指针交叉，退出循环
把 pivot（下标0）和 arr[j=4] 交换：
  下标: 0   1   2   3   4   5   6   7   8
       [2,  3,  4,  1,  5,  9,  7,  8,  6]
                        ^
                     pivot 落地
  左边[2,3,4,1] 全<5，右边[9,7,8,6] 全>5，完成分区

十、关键结论

1. partition 是快速排序的核心
   每次把 pivot 放到它最终该在的位置
   左边全 < pivot，右边全 > pivot
   使用左右双指针，扫描一遍完成，代价 O(N)
2. 随机打乱是防止退化的关键
   不打乱时：有序/逆序输入导致 O(N^2)
   打乱后：  期望时间 O(N log N)，退化概率极低
3. 递归的终止条件
   lo >= hi 时区间只剩 0 或 1 个元素，直接返回
4. 原地排序
   整个过程只用了常数额外空间（指针变量）
   不像归并排序需要额外的 O(N) 辅助数组

概率保证的直观理解：

随机化后，任意一种"坏排列"出现的概率极低。
就像连续抛硬币 1000 次都是正面，理论上可能，
但实际中几乎不会发生。
随机化算法的"失败概率" << 硬盘突然损坏的概率
所以工程上认为它和最坏情况保证一样可靠。

五、方法四：摊还分析（Amortized Analysis）

思路：不关注单次操作的代价，而是关注一系列操作的总代价平均下来每次多少。允许偶尔出现昂贵操作，只要平均代价仍然很低即可。

动态扩容数组栈（Resizing Array Stack）

这是摊还分析最经典的例子。
规则：

• 数组满时，申请一个两倍大小的新数组，把所有元素复制过去
• 数组利用率低于 $\frac{1}{4}$ 时，缩小为一半
  问题：从空栈开始，连续 $N$ 次 push，总共访问了多少次数组？
  假设 $N$ 是 2 的幂，每次扩容时复制的代价如下：
  $$\text{总代价}=\underset{\text{N次push各1次}}{\underbrace{N}}+\underset{\text{历次扩容复制}}{\underbrace{2+4+8+\cdots +2N}}=N+(2N-2)\approx 3N$$

更精确地说，扩容时还有读有写，系数约为 $5N$，但量级仍是 $O(N)$。
所以平均每次 push 的数组访问次数为：
$$\frac{5N}{N}=5\text{（常数！）}$$
命题 E：动态扩容栈的任意操作序列，从空结构开始，平均每次操作的数组访问次数为常数。

#include <iostream>
#include <stdexcept>
// 动态扩容数组栈
// 大多数 push 只花 O(1)，偶尔扩容花 O(N)
// 但摊还分析表明：平均每次操作仍是 O(1)
class ResizingArrayStack {
    int* data;      // 底层数组
    int  cap;       // 当前容量
    int  sz;        // 当前元素个数
    long long accessCount;  // 记录总数组访问次数（用于演示摊还分析）
    // 将数组容量调整为 newCap
    void resize(int newCap) {
        int* newData = new int[newCap];
        for (int i = 0; i < sz; i++) {
            newData[i] = data[i];    // 复制旧数据：sz 次读 + sz 次写
            accessCount += 2;
        }
        delete[] data;
        data = newData;
        cap  = newCap;
    }
public:
    ResizingArrayStack()
        : data(new int[1]), cap(1), sz(0), accessCount(0) {}
    ~ResizingArrayStack() { delete[] data; }
    void push(int val) {
        if (sz == cap)
            resize(cap * 2);     // 满了就扩容到两倍
        data[sz++] = val;        // 写入：1 次数组访问
        accessCount++;
    }
    int pop() {
        if (sz == 0) throw std::underflow_error("Stack is empty");
        int result = data[--sz]; // 读出：1 次数组访问
        accessCount++;
        // 利用率低于 1/4 时缩小，避免空间浪费
        if (sz > 0 && sz == cap / 4)
            resize(cap / 2);
        return result;
    }
    int  size()  const { return sz; }
    bool empty() const { return sz == 0; }
    // 打印摊还分析数据
    void printAmortized(int ops) const {
        std::cout << "总操作次数: " << ops << "\n"
                  << "总数组访问: " << accessCount << "\n"
                  << "平均每次访问: "
                  << static_cast<double>(accessCount) / ops << "\n";
    }
};
int main() {
    ResizingArrayStack stk;
    int N = 1024;  // 必须是 2 的幂，方便演示
    // 连续 N 次 push
    for (int i = 0; i < N; i++)
        stk.push(i);
    stk.printAmortized(N);
    // 预期输出：平均每次访问约 5 次（常数）
    return 0;
}

预期输出（$N=1024$）：

总操作次数: 1024
总数组访问: 4094     (约 4N，精确值取决于扩容次数)
平均每次访问: 3.998  (接近常数 4~5)

ASCII 图示：扩容代价的摊还

每次 push 的代价（纵轴=数组访问次数，横轴=第几次 push）：
代价
  |
N |                                              *   <- 第N次，扩容代价=N
  |
  |
  |                          *                      <- 第N/2次，扩容代价=N/2
  |
  |              *                                  <- 第N/4次，扩容代价=N/4
  |      *                                          <- 扩容代价=N/8
  |  * *                                            <- 普通push，代价=1
1 |* * * * * * * * * * * * * * * * * * * * * * *
  +------------------------------------------------> 操作次数
    1   2   4   8  ...  N/4  N/2   N
把高峰的代价"摊"给旁边的普通操作：
每次 push 平均代价 = (N + N/2 + N/4 + ... + 1 + N) / N ≈ 5N/N = 5（常数）

六、四种方法对比（Mermaid）

七、总结

---

方法	核心思路	典型例子	适用场景
输入模型	对输入分布建模	假设随机输入	可以合理描述输入时
最坏情况	保证任意输入的上界	链表栈 $O(1)$	安全关键、防攻击
随机化	引入随机打消坏输入	随机化快速排序	通用排序、哈希
摊还分析	总代价平均到每次操作	动态扩容栈	偶尔昂贵的数据结构

---

算法分析师的任务是尽可能深入地揭示算法的性能特性；应用程序员的任务是利用这些知识，开发出能高效解决实际问题的程序。