第2章 算法

从算法定义、五个特性与质量要求出发，推导渐近增长、时间/空间复杂度及最坏/平均情况，并建立事前分析与事后测量的证据闭环。

从两种求和方法开始

同样计算1 + 2 + ... + n，逐项累加与公式都可正确；但规模放大时，一个执行n次加法，一个只做固定次算术。数据结构与算法的关系就在这里：数据的表示决定可用操作，算法安排这些操作的顺序，而目标操作的频率又反过来影响结构选择。

先预测：在n = 10时，简单循环可能和公式一样快；这能否证明两者增长阶相同？不能。一次运行混合了时钟分辨率、编译优化、缓存和进程噪声，复杂度要从输入规模与基本操作次数推导。

#include <stdbool.h>
#include <stdint.h>
 
bool sum_loop(uint64_t n, uint64_t *out) {
    if (out == NULL) return false;
    uint64_t sum = 0;
    for (uint64_t i = 1; i <= n; ++i) {
        if (UINT64_MAX - sum < i) return false;
        sum += i;
    }
    *out = sum;
    return true;
}
 
bool sum_formula(uint64_t n, uint64_t *out) {
    if (out == NULL) return false;
    uint64_t a = n, b = n + 1;
    if (b == 0) return false;
    (a % 2 == 0) ? (a /= 2) : (b /= 2);
    if (a != 0 && b > UINT64_MAX / a) return false;
    *out = a * b;
    return true;
}

公式实现仍要处理n + 1与乘法溢出；快不能替代正确。必须相对于输入域、输出规格和计算模型解释。

算法定义与五个特性

算法定义与特性不是“能运行的一段代码”。算法可用自然语言、伪代码、流程图或程序表示；程序是某语言和机器上的实现。官方第2章把算法特性概括为输入、输出、有穷性、确定性与可行性：可以有零个或多个输入，至少有一个输出；有限步骤后结束；每一步含义明确；每一步都能通过有限次基本操作完成。

中的n可以是元素个数、顶点数、字符数或数值大小，不能只写一个字母。要能被oracle验证。

要求证明循环变量推进或递归规模缩小。不排斥随机算法，但随机源与结果分布必须成为规格。排除“枚举无限集合后选择最好答案”之类不可执行描述。

用循环不变量证明“做对且会停”

对sum_loop，第i次循环开始前可用不变量：sum = 1 + ... + (i - 1)且1 <= i <= n + 1。初始化i=1,sum=0成立；每轮加i并递增保持；终止时i=n+1，因此得到目标和。另用variant n - i + 1在每轮减少且下界为0，证明有穷性。

算法正确性不是“测试都绿”就完整结束，测试只能发现反例；不变量给出对整个输入域的结构化论证。工程中两者结合：证明核心状态关系，用边界/随机/性质测试验证实现没有偏离模型。

算法设计要求

正确性、可读性、健壮性、时间效率高和存储量低共同构成算法设计的要求。正确性至少分为：语法可执行、典型输入正确、边界输入正确、对全部合法输入满足规格。可读性让人能审查前置条件与不变量；健壮性让非法输入和资源失败得到确定处理；效率在目标规模和资源预算中评价。

算法效率的度量方法

事后统计方法在真实机器上运行实现，测量wall time、CPU、分配和cache等，能发现常数因素；但结果依赖语言、编译器、硬件、数据与系统负载。事前分析估算方法选择基本操作，按输入规模写执行次数函数，再研究函数的渐近增长，能跨机器解释规模趋势。

不是拒绝benchmark；它决定该测哪些规模与曲线。用于验证常数、局部性与系统效应。

若逐项求和每轮包含常数次比较、加法和递增，可写成：

Tloop(n)=an+bT_{loop}(n)=a n+b

公式方法在固定宽度算术模型中执行常数次操作：

Tformula(n)=cT_{formula}(n)=c

这里a,b,c依赖机器和实现，但当n增大时，主导增长分别是线性和常数。

函数的渐近增长与Big-O

帮助我们从3n+7和100n+2抽象出同一线性阶，同时保留“小规模常数仍可能重要”的工程提醒。

若存在正常数c和n0，使所有n >= n0都有0 <= T(n) <= c g(n)，则T(n) = O(g(n))。大O是渐近上界，不一定是紧确界。若同时有上下常数界，则用Theta表示紧确增长：

T(n)=Θ(g(n))⟺∃c1,c2,n0>0,  c1g(n)≤T(n)≤c2g(n)T(n)=\Theta(g(n)) \quad\Longleftrightarrow\quad \exists c_1,c_2,n_0>0,\;c_1g(n)\le T(n)\le c_2g(n)

通常报告最有信息的紧确阶，而不是把Theta(n)含糊写成也正确但无用的O(n^2)。

推导大O阶方法

推导时先选基本操作，计算执行次数；保留最高阶项；去掉与规模无关的乘法常数。顺序语句取最大增长阶，互斥分支在最坏分析中取较大分支，循环不能只数嵌套层数，要写每层迭代范围。

size_t count_pairs(const int *values, size_t n) {
    size_t equal_pairs = 0;
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = i + 1; j < n; ++j) {
            if (values[i] == values[j]) ++equal_pairs;
        }
    }
    return equal_pairs;
}

比较次数不是n*n，而是：

∑i=0n−1(n−i−1)=n(n−1)2=12n2−12n=Θ(n2)\sum_{i=0}^{n-1}(n-i-1)=\frac{n(n-1)}{2}=\frac{1}{2}n^2-\frac{1}{2}n=\Theta(n^2)

精确式说明没有自比较且每个无序对只比较一次；渐近式说明规模翻倍时主项工作约四倍。两种描述服务不同问题。

常见时间复杂度与折半过程

折半查找在有序数组中每次排除至少一半候选。经过k步后候选规模至多为n/2^k，要缩到1，需2^k >= n，因此k >= log2 n。

#include <stddef.h>
 
bool binary_search(const int *a, size_t n, int target, size_t *index) {
    size_t low = 0, high = n; /* active interval: [low, high) */
    while (low < high) {
        size_t mid = low + (high - low) / 2;
        if (a[mid] < target) low = mid + 1;
        else high = mid;
    }
    if (low < n && a[low] == target) {
        if (index != NULL) *index = low;
        return true;
    }
    return false;
}

不变量是目标若存在则始终在[low,high)；区间长度严格缩小。算法为Theta(log n)比较，但前置条件是数组按相同比较器有序。若每次先验证全数组有序，单次查询总成本会变成Theta(n)；前置条件属于系统边界，不能从局部循环隐藏。

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

最坏情况与平均情况回答不同问题；最好情况则常用于解释早停。同一算法对不同输入可能执行不同步数。最坏情况给资源和延迟上界；平均情况需要明确输入概率分布；最好情况不能代表容量规划。例如线性查找首项命中为Theta(1)，末项或不存在为Theta(n)；若目标位置均匀且一定存在，平均比较约(n+1)/2，仍为Theta(n)。

适合实时/容量保证。若没有分布假设就是空话；生产数据偏斜时应报告分位数和adversarial case。

算法空间复杂度

要声明是否计入输出、递归栈、临时buffer与预处理索引。原地算法常指额外空间O(1)，不等于完全不使用内存。

递归深度为n即使每层只有常数局部变量，也会使用Theta(n)调用栈；归并排序的临时数组通常为Theta(n)；建立索引可能用更多空间换更快查询。时间与空间不是单一排名，而是资源预算下的trade-off。

从输入模型到可复现实测

严谨结论同时包含：问题与输入模型、基本操作、精确计数或界、渐近阶、额外空间、前置条件、最坏/平均分布，以及实测环境。只写O(n)没有说明n是什么，只贴毫秒没有说明增长原因。

审计一份复杂度结论的四个常见盲区

第一个盲区是把语句数量当成输入无关的常数。源码只有十行，不代表每行只执行一次；库函数qsort、字符串复制或容器插入把循环封装在调用内部。审计时把每个非原语操作展开到约定计算模型，至少记录它依赖的长度、比较器和分配行为。相反，也不必把CPU每条指令都列出；基本操作层级只要能稳定解释增长即可。

第二个盲区是只看嵌套深度。两层循环可能是三角求和、n log n、线性甚至常数：内层范围可能依赖i，控制变量可能翻倍，也可能累计总共只前进n次。正确做法是为每个循环写迭代次数或给每个元素的总访问次数做charging argument，再求和。遇到while尤其不能从缩进猜阶，要证明variant怎样变化。

第三个盲区是忽略预处理与查询次数。建立有序数组花Theta(n log n)，之后每次折半查询Theta(log n)；建散列表期望Theta(n)，查询通常期望常数。若只有一次查询，线性扫描可能更省；若有q次查询，总成本要写成build(n) + q * query(n)，再结合更新时间与内存判断。把预处理成本悄悄移出计时窗口会制造不公平结论。

第四个盲区是把均值当成完整测量。内存分配、cache miss、分支预测、系统调度和热身会让样本偏斜；报告平均毫秒可能隐藏少量极慢值。基准应固定环境，随机化算法顺序，先校验输出，使用足够长的批次，记录median、p95/p99和离散程度。若测试数据全在cache而生产数据远大于cache，结论必须注明适用范围。

从边界分类到操作次数

任何复杂度分析都先分类输入。空输入决定初始化与越界行为；最小非空输入验证循环是否至少执行一次；一般输入用于推导；极端规模暴露整数溢出和空间上限；结构特殊输入如有序、逆序、大量重复会改变分支与递归形状。每类都要先满足同一输出规格，才允许比较速度。

以查找为例，问题不仅有n：还包括命中与否、目标位置分布、数据是否有序、比较成本是否常数。字符串key比较本身可能依赖公共前缀长度；把一次比较视为O(1)是额外计算模型假设。若key最大长度也随输入增长，应把复杂度写成n与m的函数，或明确m有固定上限。

空间分析也要按lifetime而非累计分配量判断峰值。循环中每次分配后立即释放的n个常数buffer，峰值辅助空间可能是O(1)，但分配次数仍影响时间；递归同时保留所有frame，峰值随深度增长。输出必须保存n个结果时，应明确报告output space与auxiliary space，避免用“原地”掩盖输出本身的必要成本。

最后做交叉检查：操作计数预测规模翻倍后的比例；benchmark观察是否接近；profile确认热点确实是被计数的操作。若三者不一致，不急着改结论，先检查编译器是否消除了工作、输入是否未覆盖目标分支、测量是否被I/O支配，或理论模型是否遗漏了分配与cache。复杂度分析的价值正是让偏差变成可定位问题。

本章回顾：先证明同一语义，再比较增长

  1. 算法是有限、确定、可行的操作序列，具有输入与至少一个输出；程序只是具体实现。
  2. 正确性、可读性、健壮性、时间效率与存储量共同构成算法质量。
  3. 事前分析用输入模型和基本操作推导增长，事后统计验证实现、数据与机器常数。
  4. 大O给渐近上界，Theta给紧确界；顺序、分支和循环必须按真实次数推导。
  5. 最坏情况提供上界，平均情况依赖概率分布；空间分析包含辅助buffer和递归栈。

术语表

复习本章（2 题）

讨论

评论区加载中…