笔记: 算法分析 01

2026-09-29 算法分析笔记
算法分析CS笔记

写出一个程序, 和设计一个算法, 并不是同一件事. 一个程序可以在若干测试样例上给出正确结果, 但算法设计与分析还要求我们进一步回答三个问题:

  1. 它是否对所有允许的输入都正确?
  2. 它需要多少时间和空间?
  3. 我们还能不能做得更好?

这三个问题几乎会贯穿整门算法课程. 本文从两个最基本的例子出发: 计算 Fibonacci 数和插入排序. 前者说明“同一个问题, 算法不同, 代价可能天差地别”; 后者则第一次系统展示如何证明算法正确, 又如何把一段伪代码转化为精确的运行时间分析.

1. 课程要研究什么

从程序设计一路向上看, 我们会依次遇到编程语言、数据结构、算法, 再到人工智能、大语言模型、密码学等更复杂的应用. 程序设计解决的是“如何把计算过程写出来”, 数据结构关心“如何组织数据”, 而算法设计与分析开始追问一个更本质的问题:

面对同一个计算任务, 怎样找到一个既正确又高效的计算过程?

这正是算法这门课的核心.

从这个角度看, 算法本身也是一种技术. 更快的硬件当然可以让程序变快, 但算法上的改进往往会带来数量级上的差异. 一个指数时间算法即使放在快很多的机器上, 可处理的输入规模通常也只会增加一点点; 而把算法从指数时间改成多项式时间, 才可能真正改变问题是否可计算.

课程的整体内容也围绕这一目标展开:

  1. 算法分析: 正确性, 最好、平均与最坏情况, 渐近记号, 排序.
  2. 算法设计技术: 分治, 递推式, 贪心, 动态规划, 摊还分析.
  3. 图算法: BFS, DFS, 最小生成树, 最短路, 最大流.
  4. 困难问题: NP 完全性与近似算法.

2. 什么是算法

算法并不是计算机出现之后才有的概念.

欧几里得算法用重复取余计算最大公因数; 刘徽的割圆术通过不断加倍正多边形边数逼近圆周率; 九世纪的花拉子米系统整理了十进制算术与解方程的机械步骤. “algorithm” 一词本身就来自花拉子米名字的拉丁化形式.

这些例子有一个共同点: 它们都把“如何得到答案”写成了一套明确、机械、可执行的步骤.

Definition 1 (算法)

算法是一个良定义的计算过程. 它接收一个或一组输入, 经过有限个明确步骤, 在有限时间内终止, 并产生一个或一组输出.

因此, 一个计算问题首先应被看成一个输入与输出之间的关系:

算法的任务, 就是对每一个合法输入, 按照固定规则得到满足问题要求的输出.

这个定义看似简单, 却已经暗含了几个关键要求:

  1. 明确性: 每一步都应当没有歧义.
  2. 机械性: 每一步都能由计算模型执行.
  3. 有限终止: 对合法输入, 计算过程最终停止.
  4. 规格: 我们必须先知道“什么输出才算正确”, 才能讨论算法正确性.

于是, 对以后遇到的每一个算法, 都可以固定地问三遍:

3. 大语言模型是不是算法

一个固定的大语言模型推理过程, 从输入 token 开始, 反复执行确定的神经网络运算, 再按给定采样规则生成下一个 token. 随机性本身并不会让它“不是算法”: 随机比特可以视为额外输入, 随机算法仍然是算法.

终止问题也类似. 如果系统规定遇到停止 token 或达到最大生成长度时结束, 那么整个过程具有明确的终止规则.

真正不同的是“正确性”这一问.

传统算法问题通常有明确规格. 例如排序要求输出必须是输入元素的一个排列, 且按非递减顺序排列. 因而我们可以证明一个排序算法对所有输入都正确.

而一般性的 LLM 回复通常没有这样一个数学上唯一、可检验的输出规格. 我们可以用 benchmark 或人工评价衡量它, 却很难像证明排序算法那样证明“所有回答都正确”.

因此, LLM 推理完全可以作为计算过程研究其时间与空间代价; 但本课程主要研究的是那些具有明确规格, 因而能够进行数学正确性证明的问题.

4. 第一个例子：Fibonacci 数

Fibonacci 数列满足

并且对 ,

前几项是

问题是: 给定非负整数 , 如何计算 ?

这个问题之所以适合作为算法课的第一个例子, 是因为它会很快暴露三个层次的问题:

  1. 按定义写出来的算法未必高效.
  2. “循环执行了多少次”并不等于真实计算代价.
  3. 在谈复杂度之前, 必须先说清楚采用什么计算模型.

4.1 直接照抄定义：递归算法

最自然的想法就是把递推定义翻译成程序.

Fib1(n):
    if n = 0:
        return 0
    if n = 1:
        return 1
    return Fib1(n - 1) + Fib1(n - 2)

正确性几乎不需要额外解释: 它就是 Fibonacci 数的定义本身.

困难出现在运行时间.

设 是计算 Fib1(n) 需要的基本步骤数. 对 , 有 ; 对 ,

这个递推式和 Fibonacci 数本身非常相似. 至少有

而 Fibonacci 数满足

因此 Fib1 的运行时间是指数级的. 更精确地说,

问题并不是递归这个语法本身, 而是它产生了大量重复子问题. 例如在计算 时, 我们先计算一次 ; 随后为了计算 , 又会再次计算 . 递归树越往下, 重复越严重.

4.2 为什么硬件升级救不了指数算法

因为

输入规模只从 增加到 , 工作量就大约增加 倍.

假设计算机性能每隔一段时间提高约 倍, 那么这次硬件提升所换来的, 可能只是“以前能算到 , 现在能算到 “.

这就是指数时间的危险: 硬件速度按常数倍增长, 输入规模的可承受范围却只按加法增长.

因此, 算法效率不能被当成硬件性能的附属问题. 算法本身就是一种技术.

4.3 去掉重复计算：迭代算法

既然每一项只依赖前两项, 我们可以从小到大依次算出所有需要的值.

课件中的版本保存整个数组:

Fib2(n):
    if n = 0:
        return 0

    create f[0..n]
    f[0] = 0
    f[1] = 1

    for i = 2 to n:
        f[i] = f[i - 1] + f[i - 2]

    return f[n]

循环只执行 次, 所以如果把一次加法视为常数代价, 运行时间是

与指数时间相比, 这是本质性的改进.

不过这里有一个容易混淆的细节: 课件版本与课堂 notes 中的空间复杂度并不相同.

课件中的 Fib2 保存 , 因而需要 个额外存储单元. 但如果我们只保留相邻两项, 就可以写成:

Fib-Rolling(n):
    if n = 0:
        return 0

    a = 0
    b = 1

    for i = 2 to n:
        c = a + b
        a = b
        b = c

    return b

此时额外空间变为

两种写法的算术操作次数都是 ; 区别只在于是否保留全部中间结果.

这也是算法分析里一个重要习惯: 不要只记住“某个算法的复杂度”, 而要看清楚你分析的究竟是哪一个实现. 两段实现思路相同的程序, 空间复杂度仍可能不同.

5. “一次加法”真的只需要一步吗

到这里似乎已经得到结论: Fib2 是线性时间算法.

但这个结论隐含了一个假设: 每次加法都是常数时间.

当 很大时, 这个假设不再成立.

Fibonacci 数大约满足

所以 的二进制位数约为

也就是说, 数字本身的长度随着 线性增长. 例如, 到 时已经不能再用通常的有符号 64 位整数表示 .

如果两个整数各有 位, 按逐位加法计算, 一次加法需要 个位操作. 因而 Fibonacci 的后期加法不应该继续被视为常数代价.

于是我们得到两套不同但都合理的计数方式.

5.1 按“算术操作次数”计数

如果暂时把任意整数加法都视为一步:

  1. Fib1: 次量级的操作.
  2. Fib2: 次加法.

5.2 按“位操作”计数

由于参与运算的整数最多有 位:

  1. Fib1: 大约为 个位操作.
  2. Fib2: 次加法, 每次至多处理 位, 因而为 个位操作.

更细地求和也会得到同一量级:

这说明复杂度从来不是脱离模型的绝对数字. 在说“算法是 “之前, 必须先问一句:

这里的一步到底是什么?

6. RAM 计算模型

真实计算机包含缓存、流水线、主存等复杂机制. 为了得到与具体机器无关的复杂度分析, 课程采用 RAM (Random-Access Machine) 模型.

Definition 1 (RAM 模型)

RAM 模型把计算机抽象为一台顺序执行指令的随机访问机器. 访问任意一个可寻址的内存单元都视为 时间; 对一个机器字 (word) 中的数据进行基本算术、比较、赋值和分支等操作, 也视为 时间.

word 是机器进行基本存储和运算的单位, 其长度称为字长. 为了使“访问任意内存位置需要 时间”这一假设成立, 一个 word 至少应能存下一个内存地址. 若输入规模为 , 区分 个位置至少需要 位, 因此 word-RAM 通常取

其中 为常数.

这并不表示真实机器的字长会随输入改变, 而是渐近分析中的理论假设: 随着 增大, 允许机器字长以 增长, 从而始终能够表示相应规模的地址.

字长假设也决定了哪些数据运算可以视为一步. 若一个整数能放入常数个 word, 其基本运算可视为 ; 若需要越来越多个 word 才能表示, 就必须计算多字长运算的代价.

例如 有 个二进制位, 而一个 word 只有 位, 因此 需要 个 word 才能表示. 所以在 Fibonacci 的复杂度分析中, 大整数加法不能始终视为一步.

RAM 模型有意忽略很多真实硬件细节, 例如缓存层次、不同指令的实际延迟和并行执行. 当数据搬运本身成为主要瓶颈时, 还可以采用 external-memory、cache-oblivious 等模型. 本课程则主要使用 RAM 模型.

7. 从数列进入排序

Fibonacci 例子让我们第一次看到“效率分析”. 接下来, 排序会让我们第一次完整地把以下内容放到同一个算法里:

  1. 问题的形式化定义.
  2. 算法伪代码.
  3. 正确性证明.
  4. 对具体语句执行次数的分析.
  5. 最好、平均与最坏情况.

Definition 1 (排序问题)

输入一个含 个元素的序列

输出该序列元素的一个排列

使得

这里元素未必只是数字. 实际应用中通常是“记录 + key”: 排序比较的是 key, 与 key 绑定的数据也要一起移动.

排序之所以是算法分析的经典起点, 一方面是因为它本身极其常用, 另一方面是因为许多更复杂算法都把排序作为子过程.

8. 插入排序：把新元素放进已经有序的前缀

插入排序可以类比整理手里的扑克牌.

假设左边一部分牌已经排好. 每次从右边取一张新牌 key, 从已排序部分最右端开始向左寻找位置. 所有大于 key 的元素向右移动一格, 最后把 key 放进空出来的位置.

Insertion-Sort(A, n):
    for i = 2 to n:
        key = A[i]
        j = i - 1

        while j > 0 and A[j] > key:
            A[j + 1] = A[j]
            j = j - 1

        A[j + 1] = key

这里先保存 key 非常重要. 因为后续会执行 A[j+1] = A[j], 如果不提前保存原来的 A[i], 它可能在元素右移过程中被覆盖.

而且移动必须从右向左进行. 这和在数组中为新元素“腾位置”是同一个道理.

9. 如何证明插入排序正确：循环不变式

一个程序“看起来对”, 不是证明.

对于循环算法, 最常见的证明工具是循环不变式. 它和数学归纳法本质上是同一种逻辑结构.

Definition 1 (循环不变式)

循环不变式是在循环每次迭代的某个固定位置都保持成立的命题. 证明时通常分为初始化、保持、终止三个部分.

对插入排序, 课件给出的不变式可以写得更完整一些:

Theorem 2 (插入排序的循环不变式)

在外层 for 循环每次以索引 开始时, 子数组 :

  1. 已按非递减顺序排列;
  2. 恰好由原数组最初的前 个元素组成, 只是次序可能改变.

第二条很重要. “已经有序”只说明顺序对了, 还必须保证我们没有丢掉元素、复制元素或凭空产生新元素. 排序要求输出是原输入的一个排列, 因而“元素集合保持不变”也是正确性的一部分.

证明

初始化. 第一次迭代时 . 子数组 只有一个元素, 因而天然有序, 而且显然就是原数组的第一个元素.

保持. 假设某次迭代开始时, 已经有序, 且由原来的前 个元素组成. 算法先保存 为 key. 随后从右向左检查有序前缀, 把所有严格大于 key 的元素向右移动一格.

由于前缀原本有序, 当循环停止时, key 左边的元素都不大于它, 右边被移动的元素都大于它. 因此把 key 放入 后, 仍然有序.

整个过程中只是移动原有元素并重新放回 key, 因而 仍恰好由原数组最初的前 个元素组成.

终止. 外层循环结束时 . 把 代入不变式, 得到 已按非递减顺序排列, 并且由原数组全部 个元素组成. 这正是排序问题要求的输出.

这就是循环不变式证明的标准三步:

如果把“迭代次数”看成归纳变量, 它实际上就是数学归纳法的算法版本.

10. 从伪代码到运行时间

正确性证明回答了“它会不会算错”. 接下来还要回答“它要算多久”.

设第 次外层循环中, while 条件被检查了 次. 对每一条语句赋予一个常数代价 , 就可以把总运行时间写成一个加权和.

不必执着于每个常数的具体数值. 真正决定增长率的是 如何随输入变化.

10.1 最好情况：输入已经有序

如果

那么每一轮都立即发现 . while 不会真正进入移动阶段, 对每个 只做常数次检查.

因此

一个细节是, “最好情况”不只包括严格递增序列. 如果所有元素都相等, 条件 A[j] > key 同样立刻为假, 也只需要 次 key 比较.

10.2 最坏情况：输入严格逆序

如果

那么第 轮插入时, key 必须从位置 一路移动到最前面.

这一轮需要移动 个元素. 总移动次数为

因此

10.3 平均情况：先说明概率模型

“平均运行时间”不能脱离概率分布单独讨论.

如果假设输入是 个互异元素的均匀随机排列, 那么在第 轮中, key 在前 个元素里的相对位置也是均匀的. 平均而言, 已排序前缀里大约有一半元素比 key 大, 因而仍需要 次移动.

所以

还可以从逆序对的角度看得更干净. 插入排序每消除一个逆序对, 就会执行一次相邻元素意义上的右移. 对任意一对元素, 在随机排列中它们构成逆序对的概率为 . 因而期望逆序对数是

这就解释了为什么平均情况和最坏情况虽然常数不同, 增长阶仍然相同.

11. 为什么课程通常先看最坏情况

最坏情况运行时间定义为: 在所有规模为 的输入中, 算法可能达到的最长运行时间.

它受到重视主要有三个原因.

第一, 它给出一个保证. 如果我们证明最坏情况为 , 那么任何规模为 的输入都不会比这个界更坏.

第二, 某些问题中的最坏情况并不罕见. 例如线性查找一个不存在的元素, 就必须检查整个序列.

第三, 最坏情况不需要额外假设输入来自什么概率分布, 因而适合作为不同算法之间的统一比较标准.

当然, 这不意味着平均情况不重要. 后面的随机算法、QuickSort 等内容里, 平均或期望运行时间会变得非常关键. 只是那时我们必须把随机性的来源写清楚.

12. 一个可反复使用的算法分析框架

从 Fibonacci 和插入排序两个例子中, 可以提炼出一套以后反复使用的分析顺序.

Fibonacci 的故事可以概括为

插入排序则把另一条主线建立起来:

这两条线合在一起, 就构成了算法设计与分析最基本的思维方式.

13. 本节小结

读完这一部分, 最值得真正掌握的并不是几个复杂度结论, 而是下面这些判断习惯:

  1. 算法必须有明确输入、输出、步骤与终止条件.
  2. “正确”与“高效”是两个独立问题.
  3. 对每个算法都要问: 是否正确, 运行多久, 能否更好.
  4. 指数时间和多项式时间之间的差异, 通常远大于硬件常数倍加速.
  5. 复杂度依赖计算模型; 大整数运算不能无条件视为常数时间.
  6. RAM 模型把一个 位 word 上的常见基本运算视为常数时间.
  7. 插入排序正确性的核心是循环不变式, 而不变式必须同时保证“有序”和“仍是原元素的排列”.
  8. 插入排序最好情况为 , 在均匀随机排列下平均情况为 , 最坏情况也为 .
  9. 平均情况分析必须给出概率分布; 最坏情况分析则提供对所有输入有效的保证.

以后学习渐近记号、分治、动态规划或图算法时, 形式会越来越复杂, 但基本问题不会改变:

我们要设计一个什么样的计算过程, 为什么它一定正确, 它究竟付出了多少代价, 以及还有没有更好的办法?