笔记: 算法分析 02

上一节中, 我们已经用插入排序第一次完整经历了“证明正确性—统计运行时间”的过程. 若沿着这个思路继续做下去, 一个很自然的问题会出现:

我们真的需要知道一段算法在某台机器上执行了多少纳秒, 或者精确执行了多少条指令吗?

答案通常是否定的. 算法设计与分析更关心的是: 当输入规模不断增大时, 运行时间以怎样的速度增长; 这种增长是否依赖于输入的具体排列; 为了换取更快的时间, 我们又需要付出多少额外空间.

这正是渐近分析要解决的问题.

本文以课堂第 3、4 节为主线, 并结合课件对若干细节作补充. 我们将从 RAM 模型出发, 依次建立五种渐近记号, 比较常见函数的增长速度, 再回到选择排序、冒泡排序和插入排序, 看看这些抽象记号究竟怎样服务于具体算法.

1. 从“精确计时”到“增长速度”

1.1 为什么需要计算模型

在真实计算机中, 一条指令的耗时会受到处理器、缓存、编译器、操作系统乃至内存层次结构的影响. 如果把这些细节全部纳入分析, 不同机器上的结果就很难直接比较.

在前文中, 我们已经引入了 RAM (Random-Access Machine) 模型. 这里仅回顾与复杂度分析最相关的假设: 程序顺序执行, 常见的单字长算术、比较、数据读写和控制操作均视为常数时间, 访问任意内存位置也视为常数时间.

此外, word-RAM 通常假设一个机器字包含 位, 因此一个 word 足以存放输入规模相关的地址或整数. 只有能装入常数个 word 的数据, 其基本运算才可以直接视为 ; 若一个整数需要多个 word 表示, 运算成本也应随其长度增加.

有了这一计算模型, 下面就可以把注意力从具体机器上的执行时间转向: 基本操作次数随输入规模 如何增长.

1.2 插入排序告诉了我们什么

对插入排序逐行计数时, 可以得到一个相当繁琐的表达式. 最坏情况下, 它最终具有形式

其中 取决于每条指令在具体机器上的常数成本.

如果我们的目标是比较算法, 这个表达式保留了太多不稳定的信息:

• 换一台机器, 可能变化;
• 当 很大时, 相比 越来越不重要;
• 真正决定可扩展性的, 是最高阶项所代表的增长速度.

于是我们进一步抽象, 只保留

渐近记号就是把“grows like”这句话变成严格数学语言的工具.

2. 三种非严格渐近界

以下都假设 与 在 足够大时非负.

2.1 大 : 渐近上界

直观上, 给出了 的一个“常数倍意义下的天花板”.

注意定义中的量词顺序:

我们只需要找到一个合适的常数 和一个足够大的起点 ; 在 以前发生什么并不影响渐近结论.

同一个函数通常有许多大 上界. 例如

所以, “是一个上界”与“是最紧的上界”是两回事.

2.2 大 : 渐近下界

它给出的不是天花板, 而是“常数倍意义下的地板”.

定义直接给出一个常用的对偶关系:

2.3 大 : 渐近紧界

仅有上界往往不够. 若我们已经知道一个算法运行时间至多为 , 仍然可能存在真实增长阶为 或 的可能.

要表达“确实就是这一阶”, 需要同时控制上下两侧.

例如,

因为它既是 , 又是 .

2.4 一个非常重要的区分: 不等于“最坏情况”

“最好、最坏、平均”描述的是: 我们在所有输入实例中选择哪一些输入来统计运行时间.

而 描述的是: 得到一个关于 的函数以后, 它与另一个函数之间有怎样的渐近关系.

这是两个不同维度.

例如, 插入排序的最好情况运行时间满足

当然也同样满足

因此不能把“大 “本身解释为”最坏情况”. 更准确的说法是: 算法分析中经常先定义最坏情况运行时间, 再用 或 描述它.

3. 怎样证明一个函数“不属于”某个大

证明

需要找出一组 .

因此, 否定这个命题时必须把量词全部翻转:

意味着, 对任意 和任意 , 总能找到某个 , 使得

这解释了为什么“找一个反例 “远远不够. 你必须击败所有可能的常数 和所有可能的起点 .

例如要证明

任取 , 只要选择

就有

于是任何试图用常数倍 压住 的方案最终都会失败.

4. 两种严格渐近界: 与

大 允许同阶, 例如

但有时我们希望表达“严格更慢”, 即无论给右侧乘多大的常数, 左侧最终都会小到可以被它压住.

4.1 小

大 与小 的关键差别只在一个量词:

• : 存在 一个 可以工作;
• : 每一个 最终都可以工作.

因此

但

4.2 小

例如

但

五种记号可以这样记忆:

5. 极限法: 方便, 但不是定义的替代品

如果直接从定义找常数很麻烦, 比较

往往更方便.

假设 对充分大的 成立, 而且极限存在, 则有:

• 若极限为有限非负数, 则 ;
• 若极限为正数或 , 则 ;
• 若极限为某个 , 其中 , 则 ;
• 若极限为 , 则 ;
• 若极限为 , 则 .

其中最常用的是下面这个结论.

但是, 反过来一般不成立: 并不要求比值极限存在.

因此, 极限法是很强的充分判据, 却不能取代渐近记号本身的定义.

6. 渐近记号的运算规律

这些规则之所以重要, 是因为一个算法通常由多个步骤组成. 我们希望能够先分别分析, 再把结果组合起来.

这些结论都来自定义中常数倍界的直接组合. 以乘法法则为例: 若充分大的 上有

则

加法法则则解释了算法分析中常见的“保留增长最快的一项”. 例如

7. 常见函数的增长速度

渐近分析中反复出现的函数并不多. 熟悉它们的相对增长速度, 可以让很多判断几乎一眼完成.

7.1 多项式: 最高次项决定增长阶

设

且 . 则

因为

7.2 对数严格慢于任意正次幂

对任意固定的 与 ,

因此, 无论对数上带多少个固定次数的幂, 它最终都比任意正次幂的多项式慢.

另外, 若 为常数, 则

所以在渐近复杂度中, 对数的常数底数通常可以忽略. CLRS 习惯用 , 但改成任何固定底数都只差一个常数因子.

7.3 指数严格快于任意固定次数多项式

对任意固定的 和 ,

这也是为什么指数时间算法在输入规模稍大后通常会迅速变得不可承受.

例如斐波那契数满足

因此朴素递归 Fibonacci 的递归树会表现出指数级增长.

7.4 阶乘更快

对任意固定 ,

同时

Stirling 公式进一步给出

从而

这个结论以后会在比较排序的下界中再次出现.

7.5 一条常用的增长阶梯

在只考虑课堂中常见函数时, 可以把它们大致排成

其中 为固定常数.

这里的 表示左侧相对于右侧是严格更低阶, 也就是小 的关系.

8. 空间复杂度: 时间不是唯一资源

算法消耗的不只有时间, 还会占用内存.

例如, 一个输入数组本身需要 个单元, 但若算法只额外使用几个临时变量, 则通常仍称其额外空间复杂度为

这一定义让“次线性空间”成为有意义的概念. 对于规模极大的数据, 我们甚至可能无法把全部输入同时放进内存, 只能采用 streaming 的方式逐步读入并保留少量状态.

在 RAM 模型下, 若一个算法总共只执行 步, 那么它不可能在这些步骤中访问并建立远多于 个新的工作单元, 因此通常有

实际算法设计中还经常出现时间—空间权衡: 保存更多中间结果可能减少重复计算, 而限制内存则可能迫使算法增加运行时间.

9. 最好、最坏与平均情况

对固定规模 , 不同输入实例可能触发完全不同的执行路径.

设 表示所有规模为 的合法输入, 表示算法在实例 上的运行时间.

则最好情况与最坏情况可以写成

最坏情况之所以常被优先分析, 是因为它提供了一个可靠保证: 无论输入是什么, 运行时间都不会超过这个量级.

平均情况则更微妙.

所以“平均情况”不是最好与最坏的算术平均. 没有输入分布, 就没有严格定义的平均情况.

课堂在分析插入排序时采用的典型模型是:

• 输入是 的一个排列;
• 个排列等可能出现.

下面我们就在这个模型下完成计算.

10. 三种简单排序算法

10.1 选择排序

选择排序维护一个已经确定的前缀. 第 轮在剩余元素中确定第 小的元素, 并把它放到第 个位置.

无论输入原本有序、逆序还是随机, 第 轮都需要扫描剩余部分. 因此比较次数为

所以最好、平均和最坏情况都是

若直接在原数组上交换元素, 只需要常数个临时变量, 因此额外空间为

10.2 冒泡排序

课堂中的基本冒泡排序反复比较相邻元素, 若次序错误就交换. 每一轮都会把一个元素逐渐“冒”到它应处的位置.

对于课件中的未优化版本, 即使输入已经排好序, 两层循环仍然完整执行. 因此比较次数同样是

从而

额外空间仍为

10.3 插入排序: 输入顺序真正改变了运行时间

插入排序始终维护一个已排序前缀. 处理第 个元素时, 把它向左移动, 直到插入正确位置.

InsertionSort(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 插入正确位置; 循环结束时整个数组都属于这个有序前缀.

10.4 最好情况

若输入已经有序, 处理每个新元素时, 第一次比较就发现无需向左移动.

因此总工作量只随 线性增长:

10.5 最坏情况

若输入严格逆序, 第 个元素必须越过前面的全部 个元素.

于是移动与比较次数出现求和

故

10.6 平均情况: 为什么仍然是平方级

现在假设输入是 的均匀随机排列.

在处理第 个元素时, 记它最终插入到前 个元素中的第 个位置, 其中

由于随机排列中 在前 个元素中的秩均匀分布,

若 , key 比前面所有元素都小, 共发生 次关键字比较.

若 , 它先成功越过

共 次比较; 随后再与 比较一次并停止, 因此一共是

次关键字比较.

所以第 轮的期望比较次数为

令 , 得到

对所有 求和,