0.2 算法和算法评价

§ 0.2.1 算法是什么#

一、定义#

算法是一组明确、可执行并能在有限步骤内完成某类计算任务的规则。它描述从输入到输出的求解过程，不等同于某一种编程语言写成的代码。

经典定义通常列出五项基本特征：

输入：可以有零个或多个输入。
输出：至少产生一个与任务有关的结果。
有穷性：对每个合法输入，算法在有限步骤后终止；每一步也能在有限时间内完成。
确定性：每一步的含义和下一步规则明确，不含无法解释的歧义。
可行性：每一步都能由当前计算模型中的基本操作有限次实现。

二、算法与程序#

概念	关注点	例子
算法	与语言无关的求解规则、正确性和代价	折半查找的区间缩减方法
程序	算法在特定语言、库、平台和接口下的实现	C 语言中的 `BinarySearch` 函数

一个算法可以有多种程序实现。
同一段程序可能包含多个算法，也包含输入输出、错误处理和资源管理等工程逻辑。
算法正确不代表程序一定正确；越界、整数溢出、空指针和并发竞争都可能破坏实现。

三、评价维度#

一个可用算法通常需要同时考虑：

正确性：对所有满足前置条件的输入，都产生满足后置条件的结果。
健壮性：面对非法、极端或资源不足的输入，能够给出明确处理而不是产生未定义行为。
可读性与可维护性：状态、不变量和边界清楚，便于验证和修改。
时间代价：运行所需基本操作数量怎样随规模增长。
空间代价：运行时需要的峰值额外存储怎样随规模增长。

§ 0.2.2 建立复杂度分析模型#

一、先定义输入规模#

复杂度中的 $n$ 不是固定表示“数组长度”，而是当前问题最能刻画规模的参数：

数组和线性表常用元素个数 $n$ 。
矩阵可同时使用行数 $m$ 和列数 $n$ 。
图通常需要顶点数 $V$ 与边数 $E$ 。
整数算法可能用数值大小 $N$ ，也可能用输入位数 $b=\lfloor\log_2 N\rfloor+1$ ；二者不能混用。

二、选择基本操作#

事前分析通常不计算真实秒数，而是统计能代表主导代价的操作次数，例如：

比较关键字的次数。
移动或交换元素的次数。
访问顶点、边或结点的次数。
执行散列探测或磁盘 I/O 的次数。

设基本操作次数为 $T(n)$ 。渐进分析关注 $n$ 足够大时 $T(n)$ 的增长率，暂时忽略机器速度、编译器和常数级实现差异。

三、区分输入情况#

对于同一规模 $n$ ，不同输入可能触发不同执行路径：

最好情况：该规模下代价最小的输入。
最坏情况：该规模下代价最大的输入。
平均情况：先给定输入分布，再对各输入代价求期望。
期望代价：还可以对算法自身的随机选择求期望，例如随机化快速排序。
“最好、平均、最坏”描述的是选取哪一类输入或随机过程； $O$ 、 $\Omega$ 、 $\Theta$ 描述的是函数增长界。
- 它们不是一一对应关系。

§ 0.2.3 渐进记号#

一、 $O$ ：渐进上界#

若存在正常数 $c$ 和 $n_0$ ，使所有 $n\ge n_0$ 都满足：

0\le T(n)\le c f(n),

公式解读

$T(n)$ ：实际统计的操作次数。
$f(n)$ ：用于描述上界增长率的函数。
$c$ ：允许忽略的常数倍差异。
$n_0$ ：从这个规模以后，上界持续成立。
$O$ 只保证“不比某个量级增长得更快”，不保证这个界最紧。

则记作 $T(n)=O(f(n))$ 。

例如 $3n+2$ 同时属于 $O(n)$ 、 $O(n^2)$ 和 $O(2^n)$ ；通常写最紧且最有解释力的 $O(n)$ 。

二、 $\Omega$ ：渐进下界#

若存在正常数 $c$ 和 $n_0$ ，使所有 $n\ge n_0$ 都满足 $T(n)\ge c f(n)$ ，则记作 $T(n)=\Omega(f(n))$ 。它说明增长不会长期低于这个量级。

三、 $\Theta$ ：紧确界#

若 $T(n)$ 同时属于 $O(f(n))$ 和 $\Omega(f(n))$ ，则记作：

T(n)=\Theta(f(n)).

公式解读

$\Theta(f(n))$ 同时给出同阶上界和下界。
它表示 $T(n)$ 与 $f(n)$ 只相差常数因子，增长阶相同。
若能够证明紧确界，使用 $\Theta$ 比只写 $O$ 信息更完整。

四、常见增长阶#

当 $n$ 充分大且对数底大于 1 时，常见增长关系为：

1<\log n<n<n\log n<n^2<n^3<2^n<n!.

公式解读

渐进关系比较的是增长趋势，不直接预测小规模输入的真实运行时间。
对数换底只相差常数因子，因此复杂度中通常写 $\log n$ 。
常数、缓存、分支、编译优化和数据布局仍会影响实际性能。

增长阶	常见来源	例子
$\Theta(1)$	固定次数操作	已知下标访问数组
$\Theta(\log n)$	每轮按固定比例缩小问题	折半查找
$\Theta(n)$	每个元素处理常数次	顺序遍历
$\Theta(n\log n)$	$\log n$ 层，每层总工作 $n$	归并排序
$\Theta(n^2)$	枚举元素对或三角形循环	朴素两两比较
指数或阶乘	枚举子集、选择序列或排列	穷举所有子集、全排列

§ 0.2.4 循环复杂度怎样推导#

一、顺序语句使用加法#

for (size_t i = 0; i < n; ++i) {
    use(a[i]);                 /* n 次 */
}
for (size_t row = 0; row < n; ++row) {
    for (size_t column = 0; column < n; ++column) {
        work(row, column);     /* 总计 n^2 次 */
    }
}

两个循环先后执行，总次数为 $n+n^2$ $n + n^{2}$ ，因此紧确界是 $\Theta(n^2)$ $Θ (n^{2})$ 。
- 顺序块不是把复杂度相乘，而是把操作次数相加后保留主导项。

二、独立嵌套循环使用乘法#

for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j < n; ++j) {
        visit(i, j);
    }
}

外层执行 $n$ 次。
每次外层都让内层执行 $n$ 次。
总次数为 $n\times n=n^2$ ，所以是 $\Theta(n^2)$ 。

三、内层次数依赖外层时使用求和#

for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j < i; ++j) {
        visit(i, j);
    }
}

第 $i$ 轮执行 $i$ 次，总次数为：

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

公式解读

求和项 $i$ 是第 $i$ 轮内层循环次数。
常数因子 $1/2$ 和低阶项 $-n/2$ 不改变增长阶。
这类循环不是凭“两层”判断，而是由实际迭代次数推出。

四、按比例变化产生对数#

size_t i = 1;
while (i < n) {
    if (i > n / 2) {
        i = n;                 /* 饱和到终点，避免无符号整数回绕 */
    } else {
        i *= 2;
    }
}

在抽象的倍增模型中，执行 $k$ 轮后尺度达到 $2^k$ ；当 $2^k\ge n$ 时停止，所以 $k=\lceil\log_2 n\rceil$ ，复杂度为 $\Theta(\log n)$ 。
- 代码的最后一轮可能由饱和分支直接到达 n，但对应的仍是本应越过边界的那次倍增。
数学模型中，每轮把 i 倍增。
C 实现中的饱和分支只处理最后一步：当下一次倍增可能越过 n 或机器上界时，直接把 i 置为 n。
该保护不改变迭代次数的渐进量级，却保证对任意 size_t n 都会终止。

同理，每轮把规模除以常数 $b>1$ ，也会产生 $\Theta(\log_b n)=\Theta(\log n)$ 。

五、比例循环嵌在线性循环中#

for (size_t i = 0; i < n; ++i) {
    for (size_t j = 1; j < n; ) {
        visit(i, j);
        if (j > n / 2) {
            j = n;
        } else {
            j *= 2;
        }
    }
}

外层有 $n$ 轮。
每轮内层有 $\lceil\log_2 n\rceil$ 次。
总复杂度为 $\Theta(n\log n)$ 。

§ 0.2.5 递归复杂度怎样推导#

递归分析通常先写递推式：当前调用的非递归工作，加上所有子问题的代价。

一、每次缩小 1#

long long sum_to(long long n) {
    if (n <= 0) return 0;
    return n + sum_to(n - 1);
}

时间递推为 $T(n)=T(n-1)+\Theta(1)$ ，展开 $n$ 层后得到 $T(n)=\Theta(n)$ 。若每层栈帧占常数空间，最大递归深度是 $n$ ，辅助空间也是 $\Theta(n)$ 。

二、每次缩小一半#

折半查找每轮只递归进入一半区间： $T(n)=T(n/2)+\Theta(1)$ 。展开约 $\log_2 n$ 层，所以时间为 $\Theta(\log n)$ ；递归实现的调用栈也是 $\Theta(\log n)$ ，迭代实现可以降为 $\Theta(1)$ 辅助空间。

三、分成两个一半并线性合并#

归并排序的典型递推式为：

T(n)=2T(n/2)+\Theta(n).

公式解读

2：每个问题分成两个子问题。
n/2：每个子问题的规模。
$\Theta(n)$ ：把两个有序子序列合并的本层工作。
递归树有 $\log_2 n$ 层，每层合计处理 $\Theta(n)$ 个元素，因此总时间为 $\Theta(n\log n)$ 。

扩展了解：Master 定理

考纲要求能够分析基本时间与空间复杂度，但不单列 Master 定理。遇到标准均匀分治递推时可用它辅助判断，其余情况仍应回到展开或递归树。

四、Master 定理的适用范围#

对形如 $T(n)=aT(n/b)+f(n)$ 的均匀分治递推，比较 $f(n)$ 与 $n^{\log_b a}$ ：

若 $f(n)$ 多项式意义上更小，递归叶子主导， $T(n)=\Theta(n^{\log_b a})$ 。
若二者同阶且满足常见对数扩展形式，各层工作接近相同；基础情形下 $T(n)=\Theta(n^{\log_b a}\log n)$ 。
若 $f(n)$ 多项式意义上更大且满足正则条件，本层合并工作主导， $T(n)=\Theta(f(n))$ 。

Master 定理不是所有递推式的万能公式：子问题规模不均匀、每次减 1、状态相互重叠或递推不满足条件时，应改用展开、递归树、代换证明或其他方法。

五、递归调用数不等于同时占用的栈空间#

朴素 Fibonacci 会生成大量重复调用：时间可写为 $O(2^n)$ ，更紧的增长为 $\Theta(\varphi^n)$ ，其中 $\varphi$ 是黄金比例；但任一时刻调用链最大深度只有 $n$ ，所以调用栈空间是 $\Theta(n)$ ，不是指数级。

§ 0.2.6 空间复杂度#

一、先说明采用哪种口径#

空间分析常见两种口径：

总空间：输入、输出和算法工作区全部计算在内。
辅助空间：只统计为了执行算法而额外申请的工作空间，通常不含只读输入和题目要求必须产生的输出。

数据结构正文默认报告辅助空间复杂度，若把输出或结构本体计入，会在结论旁明确说明。

二、统计峰值，而不是把每次使用机械相加#

算法空间复杂度关注运行过程中同时存活的最大空间：

循环体中的一个局部标量每轮复用，通常仍为 $\Theta(1)$ 。
递归调用的栈帧同时存活，需要按最大调用深度相加。
动态分配后未释放的对象会持续存活，应计入峰值。
先后申请的两个大缓冲区若生命周期不重叠，峰值不一定是二者之和。

三、典型例子#

迭代求和

long long sum_array(const int *a, size_t n) {
    long long sum = 0;
    for (size_t i = 0; i < n; ++i) sum += a[i];
    return sum;
}

除输入数组外，只使用 sum、i 和参数等常数个变量，辅助空间为 $\Theta(1)$ 。

递归求和

long long sum_array_rec(const int *a, size_t n) {
    if (n == 0) return 0;
    return a[n - 1] + sum_array_rec(a, n - 1);
}

最大调用深度为 $n+1$ ，每层常数空间，因此辅助空间为 $\Theta(n)$ 。

归并排序

典型数组归并排序需要长度与输入同阶的辅助数组，所以辅助数组为 $\Theta(n)$ ；递归栈为 $\Theta(\log n)$ ，峰值合计仍为 $\Theta(n)$ 。

扩展了解：均摊分析

均摊分析有助于理解动态数组扩容，但不是当前 408 数据结构大纲单列内容；主线先掌握最好、平均、最坏时间以及基本空间复杂度。

§ 0.2.7 均摊分析#

一、均摊与平均不是同一件事#

平均复杂度需要给出输入的概率分布，再计算期望代价。
均摊复杂度不假设概率分布，而是证明任意一串操作的总代价上界，再把它分摊到每次操作。

均摊分析允许某一次操作很昂贵，只要这种昂贵操作不可能频繁连续发生。

二、动态数组尾部追加#

设数组初始容量为 1，满时容量翻倍。普通追加只写入 1 次；扩容追加还要复制全部旧元素。

在容量依次从 $1,2,4,\ldots$ 扩大到至少 $n$ 时，旧元素复制总数小于：

1+2+4+\cdots+2^{\lfloor\log_2 n\rfloor}<2n.

公式解读

每一项是一次扩容时复制的旧元素数。
这是等比数列，所有历史复制量小于最终规模的两倍。
再加上 $n$ 次新元素写入，前 $n$ 次追加的总基本操作小于 $3n$ 。
因此单次尾部追加的均摊时间为 $O(1)$ ，尽管某一次扩容需要 $\Theta(n)$ 。

§ 0.2.8 算法为什么正确#

复杂度只说明代价，不证明结果正确。一个常用证明框架包括：

前置条件：输入在算法开始前必须满足什么。
循环不变量或递归假设：每轮开始/结束都保持什么事实。
保持性：一次迭代或一次递归组合为什么维持该事实。
终止性：某个量严格接近界限，保证算法最终停止。
后置条件：终止时，不变量和终止条件怎样共同推出目标结果。

完整示例：前缀求和#

long long prefix_sum(const int *a, size_t n) {
    long long sum = 0;
    for (size_t i = 0; i < n; ++i) {
        sum += a[i];
    }
    return sum;
}

可以选择不变量：每轮循环开始时，sum 等于前 i 个元素之和。

初始化：第一次循环前 i=0，前 0 个元素之和为 0，sum=0，不变量成立。
保持：本轮加入 a[i] 后，sum 成为前 i+1 个元素之和；随后 i 增加到 i+1，下一轮开始时不变量继续成立。
终止：循环条件失败时 i=n。由不变量可知，sum 等于前 $n$ 个元素之和，也就是整个数组之和。
复杂度：每个元素恰好访问一次，时间为 $\Theta(n)$ ；只使用常数个额外变量，辅助空间为 $\Theta(1)$ 。

同样的方法会在排序划分、图遍历、折半查找和树旋转中反复使用。

扩展了解：真实性能与基准测试

缓存、编译器和平台会影响真实耗时，但 408 主线首先考查渐进复杂度的基本分析。下面内容用于工程理解，不替代考试口径。

§ 0.2.9 理论复杂度与真实运行时间#

渐进复杂度用于比较增长趋势，但工程判断还需要测量：

常数因子：哈希、比较、内存分配和系统调用的单次代价不同。
缓存与局部性：连续数组的线性扫描可能比指针跳转快很多。
输入分布：分支预测、冲突分布和枢轴质量会改变实际路径。
编译与平台：向量化、内联、字长和内存层次影响耗时。
规模区间：渐进更优的算法可能在小输入上被初始化开销抵消。

正确做法是：先用复杂度排除增长不可接受的方案，再在真实数据和平台上基准测试候选实现。基准测试不能替代理论分析，因为有限样本不保证未知规模下的增长上界。

§ 0.2.10 常见误解与边界#

$O$ 不等于最坏情况， $\Omega$ 不等于最好情况， $\Theta$ 也不等于平均情况。
- 应先选最好/平均/最坏代价函数，再用渐进记号描述该函数。
两层循环不必然是 $O(n^2)$ 。
- 真实次数可能是 $n\log n$ 、 $n$ 或其他求和结果。
递归时间不等于递归深度。
- Fibonacci 的调用总数呈指数增长，但最大调用深度只有线性。
空间复杂度不是代码行数，也不是累计申请次数。
- 应统计指定口径下的峰值存活空间。
原地算法不一定严格零额外空间。
- O(1) 表示额外空间不随输入规模增长，仍可使用常数个变量。
均摊代价不保证单次延迟。
- 动态数组追加均摊 $O(1)$ ，扩容那一次仍是线性时间。
复杂度相同不代表实际性能相同。
- 数据布局、缓存和常数因子可能在实际规模中占主导。

理解检查

为什么不能把 $O$ 直接解释成最坏情况？
for i=0..n-1 内部执行 j*=2 的循环，为什么是 $\Theta(n\log n)$ ？
为什么朴素 Fibonacci 的时间可为指数级，而调用栈空间只有线性？
（扩展）动态数组尾部追加的均摊 $O(1)$ 是否意味着每一次追加都为 $O(1)$ ？

参考回答：

$O$ 是函数的渐进上界；最好、平均、最坏是在同一规模下选择不同输入代价。最坏代价函数也可以有 $O$ 、 $\Omega$ 和 $\Theta$ 描述。
外层有 $n$ 轮，每一轮内层把 j 按 2 倍增长，执行 $\Theta(\log n)$ 次，相乘得到 $\Theta(n\log n)$ 。
时间统计递归树中的全部调用，空间只统计同时活跃的最长调用链；分支返回后，其栈帧会被复用。
不是。扩容操作单次需要复制已有元素，最坏为 $\Theta(n)$ ；但任意前 $n$ 次追加的总复制量为 $O(n)$ ，所以平均分摊为 $O(1)$ 。

总结#

分析算法前要先确定输入规模、基本操作和最好/平均/最坏等输入口径，再用 $O$ 、 $\Omega$ 或 $\Theta$ 描述相应代价函数。
循环代价来自真实迭代次数，递归时间来自全部调用工作，辅助空间来自峰值同时存活状态；循环层数、递归调用数都不能直接替代推导。
复杂度不证明正确性；应结合前置条件、不变量、保持性、终止性与后置条件完成论证。Master 定理、均摊分析和真实性能测量已单独折叠为扩展。

← 0.1 数据结构基本概念 | 00-数据结构 | 1.1 线性表 →

§ 0.2.1 算法是什么#

一、定义#

二、算法与程序#

三、评价维度#

§ 0.2.2 建立复杂度分析模型#

一、先定义输入规模#

二、选择基本操作#

三、区分输入情况#

§ 0.2.3 渐进记号#

一、OOO：渐进上界#

二、Ω\OmegaΩ：渐进下界#

三、Θ\ThetaΘ：紧确界#

四、常见增长阶#

§ 0.2.4 循环复杂度怎样推导#

一、顺序语句使用加法#

二、独立嵌套循环使用乘法#

三、内层次数依赖外层时使用求和#

四、按比例变化产生对数#

五、比例循环嵌在线性循环中#

§ 0.2.5 递归复杂度怎样推导#

一、每次缩小 1#

二、每次缩小一半#

三、分成两个一半并线性合并#

四、Master 定理的适用范围#

五、递归调用数不等于同时占用的栈空间#

§ 0.2.6 空间复杂度#

一、先说明采用哪种口径#

二、统计峰值，而不是把每次使用机械相加#

三、典型例子#

§ 0.2.7 均摊分析#

一、均摊与平均不是同一件事#

二、动态数组尾部追加#

§ 0.2.8 算法为什么正确#

完整示例：前缀求和#

§ 0.2.9 理论复杂度与真实运行时间#

§ 0.2.10 常见误解与边界#

总结#

一、 $O$ ：渐进上界#

二、 $\Omega$ ：渐进下界#

三、 $\Theta$ ：紧确界#