Lecture 4: 算法分析：大 O 记号与运行时间估算（Big-O & Algorithmic Analysis）（对应课程真实讲座 L07）

目录 · ← l3 · l5 →

Lecture 4: 算法分析：大 O 记号与运行时间估算（Big-O & Algorithmic Analysis）（对应课程真实讲座 L07）

概述

本讲回答一个贯穿全课程的问题：“这个算法到底快不快？”先论证两种直觉方案都不可靠——用秒表计时受机器与负载干扰，逐条数指令又繁琐且无意义；随后引入大 O 记号（Big-O）：用“输入变大时工作量如何增长”来刻画算法的本质快慢。接着建立常见增长函数族的直觉（常数、对数、线性、n log n、二次、指数……），推导求和恒等式 1+2+…+n = n(n+1)/2，并据此解释为何 add 均摊很快而 insert(0,·) 慢到爆炸，最后学会根据增长阶数估算可处理的问题规模。 对应官方 L07（7/1，Big-O and Algorithmic Analysis）一讲；官方随讲给出 Prezi 与“对数运行时的推导”补充视频。

核心概念与算法原理

1. 为什么“墙钟计时”与“数指令”都不靠谱

问题定义：如何公平地比较两个解决同一问题的算法谁快？ 直观解释：官方 L07 先泼两盆冷水。方案一：直接掐秒表（墙钟时间）——同一程序在不同机器、不同负载下时间天差地别；后台开个浏览器都能干扰结果；测试用例大小不公平，结论就失真。方案二：数代码执行了多少条“操作”（赋值、比较、算术、函数调用……）——听起来更“公平”，但很容易数漏（i++ 其实含一次算术+一次赋值，v[i] 背后藏着一乘一加的内存寻址……），而且不同指令在 CPU 上的时钟周期不同，编译器还会优化改写你的代码——数出来的 4n+4 这种数字基本没有意义（官方原话：这是“傻瓜的差事”）。 结论：我们真正该关心的是增长率——当输入规模 n 增大时，工作量以什么“形态”增长：是翻倍就翻倍（线性），还是翻倍就变四倍（二次）？大 O 记号就是描述这种形态的语言。

2. Big-O 的直觉与（非正式）定义

问题定义：给运行时间函数 T(n) 找一个最简“成长形状”来描述它。 直观解释：设输入规模为 n（数组长度、字符串长度、某个整数等）。Big-O 回答：“当 n 变得足够大时，T(n) 大致像什么函数在长？”它只关心“最高阶项”，忽略常数系数与低阶项——因为这些在 n 巨大时才是决定命运的。 严谨定义（了解即可）：称 T(n) = O(f(n))，若存在常数 c 与 n₀，使得对所有 n ≥ n₀ 都有 T(n) ≤ c·f(n)。意思是：从某个足够大的 n 开始，T(n) 的曲线总被 c·f(n) 压住。 化简法则（官方 L07 三步流程）：

1. 假设输入任意大；
2. 找到执行次数最多的语句，统计它跑了多少次（机器无关的近似）；
3. 扔掉常数系数、只留最高阶项 → 大 O 结果。 例如 T(n) = 4n + 4 → O(n)；T(n) = (1/6)n² + 1000n → O(n²)；T(n) = 6n + 2ⁿ → O(2ⁿ)（指数项吞掉一切多项式）。

3. 常见增长函数族与直觉

工作量(操作数)
  ^
  |                            2ⁿ :每加 1 输入就翻倍,爆炸式
  |                          ╱
  |                      n² ╱   :n 翻倍 → 工作量 ×4
  |                    ╱
  |              n·log n     :排序类算法的典型
  |            ╱
  |        n ╱   :n 翻倍 → 工作量 ×2(线性)
  |      ╱
  |  log n :n 翻倍只多 1 步,几乎贴着地面
  | 1 ─────  :常数,与 n 无关
  +───────────────────────────────────► n(输入规模)

增长顺序铁律（n 巨大时）：1 < log n < n < n log n < n² < 2ⁿ < n!。前两名几乎贴地、后两名都是“灾难级”，中间的差距也动辄千万倍。官方 L07 特别提醒一个常见误解：不要把 O(log n) 看成“O(1) 与 O(n) 之间的一半”——对数增长极其接近常数：输入从 1 涨到 10 亿，log₂ 只从 0 涨到 30。

4. 求和恒等式：1+2+…+n = n(n+1)/2

问题定义：insert(0,·) 连续 n 次总共搬移 1+2+…+n 个元素，这串和到底等于什么？ 推导（官方 L07 同款手法）：设 S = 1 + 2 + … + (n−1) + n，把它倒过来再写一遍，两式相加：

  S =   1   +   2   + … + (n−1) +   n
+ S =   n   + (n−1) + … +   2   +   1
--------------------------------------
 2S = (n+1) + (n+1) + … + (n+1) + (n+1)      ← 共 n 个 (n+1)
 2S = n(n+1)
  S = n(n+1)/2

关键结论（官方点名要记住）：1+2+…+n = n(n+1)/2，它的数量级是 O(n²)（因为 (n²+n)/2 的最高阶是 n²）。凡是在循环里看到“第 i 次做 i 件事”，总工作量多半就是这条恒等式。

5. 幕后：v.add 的“均摊 O(1)” vs v.insert(0,·) 的 O(n)

问题定义：官方文档说 add 是 O(1)、insert(0,·) 可达 O(n)，两者差在哪？ add 的均摊机制：vector 底层是一块连续数组。末尾有空位时，add 只写一个新元素（O(1)）；当容量（capacity）恰好用尽，vector 会扩容：申请一块更大的内存（常见策略是翻倍）、把 n 个旧元素全部拷过去、释放旧块——单看这一次是 O(n)。但因为容量翻倍，这次 O(n) 之后要再等 n 次 O(1) 的 add 才会再次扩容：

容量=4,已满:   [1][2][3][4]        ← push_back(5): 放不下!
扩容到 8:     [1][2][3][4][ ][ ][ ][ ]   ← O(n)=4 次拷贝,腾出 4 个空位
再写 5:       [1][2][3][4][5][ ][ ][ ]
   —— 接下来 3 次 add 都只需写 1 个位置,把刚才的 O(n) 摊薄

n 次 add 的总成本 ≈ n 次 O(1) + 少数几次 O(n) 扩容 ≈ O(n)，平均每次 O(1)——这就是“均摊（amortized）O(1)”的含义：单次可能贵，长期平均便宜。 insert(0,·) 为什么是 O(n)：在开头插一个元素，必须把现有的每一个元素都右移一格腾位置；第 i 次插入要搬 i 个元素，n 次共搬 1+2+…+n = n(n+1)/2 ≈ O(n²)。官方在 L04/L07 的课上实测（TIME_OPERATION，规模 5 万→50 万）：add 版耗时从毫秒级缓慢爬升，insert 头部版则爆炸式增长，两版差距从十几倍扩大到数百倍。中间位置插入同理要搬一半元素（O(n)），只有紧贴末尾插入才接近 O(1)（写的元素数 = size − index + 1）。

6. 由增长阶数估算运行时间（规模估算）

问题定义：已知某 O(f(n)) 函数在 n₀ 时耗时 t₀，如何预测 n₁ 时的耗时？ 方法：运行时间按“输入规模比值的 f 次方”放大。设 k = n₁/n₀：

• 线性 O(n)：耗时 ×k。例：n=50 用 100ms → n=100 用 200ms。
• 二次 O(n²)：耗时 ×k²。例：n=50 用 100ms → n=100 用 400ms；若 n 冲到 100 万，放大 (10⁶/50)² = 4×10⁸ 倍 → 100ms × 4×10⁸ = 4×10¹⁰ ms ≈ 463 天！
• 指数 O(2ⁿ)：耗时 ×2^(n₁−n₀)。例：n=5 用 100ms → n=30，放大 2²⁵ ≈ 3355 万倍 → 约 38.8 天。官方提醒：n 只加了 25，就从 0.1 秒变一个多月——输入每 +1，运行时间翻倍，这是识别 O(2ⁿ) 的“指纹”。
• 对数 O(log n)：n 翻倍只多 1 步。n=10 亿时 log₂n ≈ 30——只需约 30 步就能处理 10 亿规模（因为 2³⁰ ≈ 10 亿），这正是二分查找等对数算法的“可怕之处”（官方 L07 称之为 logarithmic runtimes 的震撼）。

判断口诀：n 翻倍 → 时间翻倍 = 线性；变 4 倍 = 二次；只加常数 = 对数；直接翻倍翻倍再翻倍 = 指数。O(n²) 函数不一定“慢”，O(n) 函数也不一定“快”——大 O 只描述增长趋势，不承诺具体秒数（官方 L07 特别指出这一点，并举例自己实测过 n=1 万仅 14ms 的 O(n²) 函数）。

代码示例与实现详解

示例 1：亲手测量 O(n) 与 O(n²)——翻倍实验

// 文件: growth_demo.cpp
// 演示: 规模翻倍时, push_back 总耗时近似翻倍(线性), 头部插入总耗时近似 ×4(二次)
#include <chrono>
#include <iostream>
#include <vector>
using namespace std;

double timeAppend(int n) {                // n 次在末尾追加(push_back)
    vector<int> v;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < n; i++) v.push_back(i);
    auto t1 = chrono::steady_clock::now();
    return chrono::duration<double, milli>(t1 - t0).count();
}

double timePrepend(int n) {               // n 次在头部插入(insert(begin()))
    vector<int> v;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < n; i++) v.insert(v.begin(), i);
    auto t1 = chrono::steady_clock::now();
    return chrono::duration<double, milli>(t1 - t0).count();
}

int main()
{
    cout << "n       push_back(ms)   insert(begin)(ms)   头部/末尾" << endl;
    double prevP = -1;
    for (int n = 2000; n <= 32000; n *= 2) {     // 规模每次翻倍
        double tA = timeAppend(n);
        double tP = timePrepend(n);
        cout << n << "    " << tA << "    " << tP << "     " << tP / tA;
        if (prevP > 0) {                         // 与上一档头部耗时比
            cout << "   (头部较上一档 ×" << tP / prevP << ")";
        }
        cout << endl;
        prevP = tP;
    }
    return 0;
}

【代码做什么】：对 n = 2000、4000、…、32000 逐档测量“n 次末尾追加”与“n 次头部插入”的总耗时，打印两列及比值。预期：push_back 档间近似 ×2（线性）；insert(begin) 档间近似 ×4（二次），两列差距越拉越大。

【实现机制解说】：为什么头部插入档间是 ×4？第 i 次 insert(begin()) 要搬 i 个元素，n 次共搬 1+2+…+n ≈ n²/2 次——n 翻倍 → 总搬移 ×4，这就是求和恒等式的活教材（O(n²) 的来源）。push_back 则每次几乎只写一个位置，偶尔触发一次 O(n) 扩容，均摊后总 O(n)，所以翻倍 → 总时间约 ×2。注意两次测量都在同一进程内进行、用 steady_clock 取墙钟差，量级上足以看清增长形态；若机器抖动较大，可把档位起点调大或每档重复几次取平均——但不要用绝对毫秒数跨机器比较，这正是本讲开头“墙钟不可靠”的教训。

示例 2：用“操作计数器”实证三种增长形态 + 验证求和恒等式

// 文件: opcount_demo.cpp
// 演示: 用计数器亲眼看到 线性 / 二次 / 对数 的执行次数; 验证 1+…+n = n(n+1)/2
#include <iostream>
using namespace std;

long countLinear(int n) {                 // 线性: 循环 n 次
    long ops = 0;
    for (int i = 0; i < n; i++) ops++;
    return ops;                            // 恒等于 n
}

long countNested(int n) {                 // 二次: 双层循环, 恰好执行 n×n 次
    long ops = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) ops++;
    return ops;
}

long countHalving(int n) {                // 对数: 反复减半, 次数 ≈ log2(n)+1
    long ops = 0;
    while (n > 0) { n /= 2; ops++; }
    return ops;
}

int main()
{
    cout << "== 表 A: 线性 vs 减半(对数) ==" << endl;
    cout << "  n         线性次数   减半次数" << endl;
    for (int n : {1000, 1000000, 100000000}) {
        cout << "  " << n << "   " << countLinear(n) << "   "
             << countHalving(n) << endl;
    }
    cout << "  (若 n=10 亿: 线性要 10 亿步, 减半只需 30 步, 因为 2^30≈10^9)" << endl;

    cout << "== 表 B: 双层循环实际次数 == n² ==" << endl;
    cout << "  n     实际次数      n×n" << endl;
    for (int n : {500, 1000, 2000, 4000}) {
        cout << "  " << n << "   " << countNested(n) << "    " << (long)n * n << endl;
    }

    // 求和恒等式: 循环累加 vs 闭式公式, n=1..100000 全量核对
    long long check = 0;
    bool ok = true;
    for (long long n = 1; n <= 100000; n++) {
        check += n;
        long long formula = n * (n + 1) / 2;
        if (check != formula) { ok = false; break; }
    }
    cout << (ok ? "恒等式成立: 1+2+…+100000 = " : "恒等式出错!")
         << check << " = 100000×100001/2" << endl;
    return 0;
}

【代码做什么】：用真实的计数器展示三种增长：线性计数器等于 n；减半计数器在 n=1000/10⁶/10⁸ 时只从 10 涨到 27；双层循环计数器恰等于 n²（表 B 三列一致，眼见 O(n²) 的来源）；最后把 1 累加到 10 万，与 n(n+1)/2 公式逐项核对，验证恒等式。

【实现机制解说】：三个计数器函数就是三种复杂度的“活体标本”。countHalving 揭示 O(log n) 的模式——每轮把输入除以 2，且每轮只做 O(1) 工作，则总轮数 ≈ log₂n：n=10⁸ 只跑 27 轮，n=10⁹ 也才 30 轮（2³⁰ ≈ 10 亿，官方 L07 引用的震撼数字）。countNested 内层循环独立执行 n 次、外层又套 n 次，总执行恰好 n² 次——这是 O(n²) 最直白的来源。恒等式验证采用“暴力求和 vs 闭式公式”对拍：C++ 里 n * (n + 1) 若 n 是 int 可能溢出，故这里用 long long 并先乘后除——顺带复习了类型宽度与运算顺序的坑（除以 2 放最后才能保证 (n+1) 为奇数时也整除）。

示例 3：规模估算器——把“n 翻倍会怎样”变成数字

// 文件: estimate_demo.cpp
// 演示: 由基准 (n0, t0) 预测 n1 的耗时(线性/二次/指数三种增长)
#include <iostream>
using namespace std;

// 多项式增长: power=1 → 线性(×k), power=2 → 二次(×k²)
double predictMs(int n0, double t0ms, int n1, int power)
{
    double k = (double)n1 / n0;          // 输入规模放大倍数
    double factor = 1.0;
    for (int i = 0; i < power; i++) factor *= k;
    return t0ms * factor;
}

// 指数增长: 每多 1 输入翻一倍 → 放大 2^(n1-n0) 倍
double predictExpMs(int n0, double t0ms, int n1)
{
    double factor = 1.0;
    for (int k = n0; k < n1; k++) factor *= 2;
    return t0ms * factor;
}

int main()
{
    cout << "官方同款例题(基准: n=50 用 100ms):" << endl;
    cout << "  线性 n=100:   " << predictMs(50, 100, 100, 1) << " ms" << endl;   // 200
    cout << "  二次 n=100:   " << predictMs(50, 100, 100, 2) << " ms" << endl;   // 400
    cout << "  二次 n=1e6:   " << predictMs(50, 100, 1000000, 2)
         << " ms = " << predictMs(50, 100, 1000000, 2) / 1000.0 / 3600 / 24
         << " 天" << endl;                                                       // ≈463 天
    cout << "  指数 n=5→30:  " << predictExpMs(5, 100, 30)
         << " ms = " << predictExpMs(5, 100, 30) / 1000.0 / 3600 / 24
         << " 天" << endl;                                                       // ≈38.8 天
    return 0;
}

【代码做什么】：把“规模估算”做成函数：给定基准点 (n₀, t₀) 与目标 n₁，线性增长按 ×(n₁/n₀) 放大、二次按平方放大、指数按 2 的差次方放大；main 直接复算官方 L07 的三道例题并换算成“天”，让数字自己说话。

【实现机制解说】：估算的本质是比例推理——我们从不预测绝对秒数，只预测“相对基准放大了多少倍”，因此与机器、语言无关，这正是大 O 的价值。指数分支里 for (k = n0; k < n1; k++) factor *= 2 累乘 n₁−n₀ 次，避开浮点溢出地算出 2^(n₁−n₀)；二次分支的 for 循环等价于 factor = k * k，写循环是为了与“幂次可扩展”的教学语义一致。结果对照官方数字：二次在 n=10⁶ 时约 463 天、指数在 n=30 时约 38.8 天——注意这些预测都锚定在 n=50 用 100ms 这个假设基准上；官方 L07 强调，换一个基准点（例如实测 n=10⁴ 只要 14ms 的 O(n²) 函数）绝对数字会完全不同，但增长形态不变。这也解释了为何不要拿别人的秒数吓自己：该警惕的是增长阶数，不是某个绝对值。

复杂度分析

附：空间复杂度同规则——只关心“随 n 增长的内存形态”，例如 vector 扩容临时占 O(n) 额外空间、树与哈希表存 n 个元素占 O(n)。

关键要点

• 别用秒表比算法：机器、负载、用例都会污染结论；大 O 只谈增长形态。
• 化简法则：扔常数、留最高阶——4n+4 → O(n)，(1/6)n²+1000n → O(n²)。
• 记住增长链条 1 < log n < n < n log n < n² < 2ⁿ，以及“对数≈贴着常数、指数≈灾难”。
• 求和恒等式 1+2+…+n = n(n+1)/2 = O(n²)：见到“第 i 次做 i 件事”就想起它。
• 判断指纹：输入翻倍，时间翻倍=线性、×4=二次、只加常数=对数、整体再爆炸=指数。

常见陷阱与注意事项

• 用墙钟秒数跨机器比较：同一程序两台机器差 10 倍很正常。规避：只比较同一环境下的相对增长，或干脆用操作计数/大 O 表述。
• 拿“单个 O(n) 函数慢”下结论：大 O 不承诺常数大小——O(n) 里藏着 1000n 也可能比 O(n²) 的 0.001n² 在中小规模更慢。规避：大 O 用于讨论 n 很大时的趋势。
• 把 O(log n) 当“介于常数与线性之间的一半”：对 10 亿输入 log 只需 30 步，它贴着常数跑。规避：背下“2³⁰≈10⁹”这个数感锚点。
• 忘记均摊：说“push_back 是 O(n)”不完全错但会误导——单次可能 O(n)，长期平均 O(1)。规避：描述为“均摊 O(1)”。
• 溢出破坏估算/求和：n*(n+1)/2 中 int 相乘可能溢出；2^n 也别真算。规避：用 long long，指数估算用对数或累乘。
• 把双层循环一律当 O(n²)：内层若与 n 无关（如固定 100 次）则整体仍是 O(n)。规避：数清内外层各自的迭代次数再相乘。
• 规模估算忘了基准：所有“预测天数”都锚定在某个假设基准上，基准不同绝对数字全变。规避：先明确“什么规模、多少时间”的基准再外推。

思考题（带答案）

问题 1：函数 A 对 n 个元素做两遍单层扫描，函数 B 对同样输入做一层嵌套循环。分别求大 O，并说明“A 一定比 B 快吗”。 答案：A 是 2n 次操作 → O(n)；B 是 n² 次 → O(n²)。大 O 上 A 优于 B，但不保证 A 在每个具体 n 都快——若 A 的单步代价很高而 B 极简，小规模时可能反超；不过 n 足够大后 O(n) 必然碾压 O(n²)。这正是大 O 只谈趋势、不谈常数的含义。

问题 2：某算法在输入 n=10 时耗时 1ms，在 n=20 时耗时 4ms，在 n=40 时耗时 16ms。它大致是什么复杂度？n=160 时预计多久？ 答案：n 翻倍 → 时间 ×4，符合二次 O(n²)。从 40 到 160 是两轮翻倍（40→80→160），时间 ×16：16ms × 16 = 256ms。（也可直接按比例 (160/40)² = 16 计算。）

问题 3：为什么说“在 vector 开头反复 insert 的总成本是 O(n²)”，用求和恒等式解释，并给出 n=10⁵ 时的搬移次数量级。 答案：第 i 次在开头插入要右移 i 个元素，n 次总搬移 = 1+2+…+n = n(n+1)/2 ≈ n²/2，最高阶 n² → O(n²)。n=10⁵ 时约搬 5×10⁹ 个元素，即便每秒搬 10⁹ 个也要约 5 秒；而同样的 n 次 push_back 均摊总成本只有 O(n)。这就是为什么“优先往末尾堆数据”是铁律。