算法的代价

摘要

到目前为止，本课程只用一个问题来评判算法：它们是否做到了所说的事？本课加上第二个问题，它决定一个正确的程序在实践中是否可用：它的代价有多大？代价首先不借助时钟来衡量，而是数出主导操作执行了多少次，结果它是数据规模 $n$ 的函数。这个函数重要的不是它在给定的 $n$ 处的值，而是它如何增长：一张列出 $n$ 、 $n \log n$ 、 $n^2$ 和 $2^n$ 的表表明，算法之间的差异在十个数据时看不出来，在一百万个数据时却成了鸿沟。大 $O$ 记号被作为这些增长阶的简写来介绍，不给形式定义，只举课程中已经见过的例子：辗转相除法，对数阶；向量求和，线性阶；比较所有的元素对，平方阶；朴素的斐波那契，指数阶。随后用 <chrono> 的时钟 std::chrono::steady_clock 来测量，并说明为什么一次测量会骗人，为什么要在开启优化、不用检测器（sanitizer）的条件下测量，以及如何用预测来对照测量：当 $n$ 加倍时，线性算法的时间加倍，平方阶算法的时间变为四倍。

学习目标

以数据规模 $n$ 的函数形式，数出含一层或两层循环的算法的主导操作次数。
将算法归类为常数阶、对数阶、线性阶、 $n \log n$ 阶或平方阶，并预测 $n$ 加倍时其时间如何变化。
用 std::chrono::steady_clock 测量运行时间，并把测量结果与预测相比较。
针对给定的数据规模在两个算法之间作出选择，并用增长阶说明选择的理由。

数操作次数

第二个问题

设计正确的循环和递归两课教我们证明一个算法是正确的：它会终止，并且它的结果满足后置条件。然而，数值算法一课展示了两种同样正确的素性检验，一种大约做 $n$ 次除法，另一种大约做 $\sqrt{n}$ 次；递归一课则展示了计算 $F_{30}$ 的两种正确方法，一种调用 $2\,692\,537$ 次，另一种只做 29 次加法。如果是这样，正确性就不足以作出选择：在两个正确的算法中，一个可能瞬间作答，另一个却可能直到答案已经无关紧要时还没有结束。因此，对一个算法要问的第二个问题是：它的代价有多大。

代价可以用时钟来测量，第四节就会这样做。但一次运行的时间取决于机器、编译器、编译器的选项，以及计算机同时在做的其他事情；从它推不出该算法在另一台机器上的任何情况。不依赖于这些因素的，是算法所走的步数。由此得出本课的第一个决定：用计数来衡量代价，而把时钟留给对计数的检验。

规模与主导操作

数出所有的步骤（每次加法、每次比较、每次下标自增、每次内存访问）既繁琐又无用，因为几乎所有步骤都按固定比例伴随着一个主要步骤。因此要选出主导操作：它的执行次数不少于其他任何操作（相差一个常数因子以内），因而可以代表全部操作。在向量元素求和中，它是加法；在求最大值中，它是比较；在素性检验中，它是除法。它的执行次数表示为输入规模的函数，输入规模记作 $n$ ：向量的元素个数、被检验的数、数位的个数。

一个简单的循环遍历含 $n$ 个元素的向量，并对每个元素做固定量的工作，它执行其主导操作 $n$ 次。相反，求非空向量的最大值时，先把第一个元素作为候选，再把其余每个元素与它比较： $n - 1$ 次比较。 $n$ 与 $n - 1$ 之间的差别是真实的，但正如第三节将会看到的，它丝毫不改变重要的东西。

最坏情况

有些算法在同样规模的数据上执行的操作次数并不总是相同。在向量中查找一个值，一直遍历到找到为止：如果该值在第一个位置，只做一次比较；如果它不在向量中，则做 $n$ 次。要讨论它的代价，就要在两种情形中选一种，通常的选择是最坏情况：在所有规模为 $n$ 的输入中操作次数的最大值。理由与契约为所有满足前置条件的输入而写的理由相同：最坏情况是一种保证，最好情况只是一种希望。所以线性查找在最坏情况下的代价是 $n$ 次比较；本课不加限定地说“代价”时，指的就是最坏情况的代价。

嵌套循环

循环一课教过如何数两层嵌套循环的轮数。如果内层总是做 $m$ 轮，并且外层 $n$ 轮中的每一轮都是如此，那么内层循环体执行 $n \cdot m$ 次。如果内层依赖于外层，就逐行求和。处理集合时最常见的情形是所有的元素对：把每个元素与它后面的每个元素比较，例如判断一个向量中是否有重复元素。

C++ 程序

#include <print>int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}：{:>10} 次比较；n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

输出

n =     10：        45 次比较；n(n - 1)/2 = 45n =    100：      4950 次比较；n(n - 1)/2 = 4950n =   1000：    499500 次比较；n(n - 1)/2 = 499500n =  10000：  49995000 次比较；n(n - 1)/2 = 49995000

计数器占据了真实算法所做比较的位置。在外层的第 $i$ 轮中，内层从 $i + 1$ 到 $n - 1$ ，共 $n - 1 - i$ 轮；所以总数是 $(n - 1) + (n - 2) + \cdots + 1 + 0$ ，即循环一课中的那个和：

\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

输出对每个规模都证实了这个公式。计数器用 long long，是因为从 $n$ 约为六万五千起，元素对的个数就超过了 int（在这个平台上为 32 位）的最大值；公式先转换再相乘也是出于同样的理由：平方阶算法的计数器比数据早得多就会溢出。

现在就请注意第三节将要推广的现象： $n$ 乘以 10 时，比较次数大约乘以 100。十个数据时，45 次比较；一万个数据时，将近五千万次。

摘要