基础非数值算法

递归

若一个过程直接或间接调用自身，就称为递归。写递归程序前要先找到两件事：规模更小的同类子问题，以及一定能到达的终止条件。缺少前者只是循环调用，缺少后者则会耗尽调用栈。

阶乘和欧几里得算法是最简单的例子：

递归调用时，返回地址、参数和局部变量组成活动记录压入系统栈。因而递归深度为 \(h\) 时，除实际运算外还要占 \(O(h)\) 的栈空间。它的优点是结构接近数学定义，代价是调用开销、可能的重复计算以及栈溢出风险。

Fibonacci 数列与重复子问题

直接按定义计算

long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

会反复计算同一子问题，调用树规模呈指数增长。只保留相邻两项即可改成 \(O(n)\) 时间、\(O(1)\) 额外空间：

long long fib(int n) {
    if (n <= 1) return n;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

这也是动态规划的雏形：识别重叠子问题，保存有用的中间结果。

汉诺塔

要把 \(n\) 个盘从柱 A 移到柱 C，可先把上面的 \(n-1\) 个移到 B，再移动最大盘，最后把 \(n-1\) 个从 B 移到 C。移动次数满足

递归程序很短，但指数级工作量来自问题本身，改写成非递归形式也不会降低移动次数。非递归算法可以利用盘号奇偶性和合法移动规则生成同一序列。

递归的消除

尾递归是指递归调用的结果被直接返回，之后没有待完成的运算。把累积状态改成循环变量即可消除调用栈。例如真正的尾递归阶乘需要把乘积作为参数：

long long factorial_tail(int n, long long acc = 1) {
    if (n == 0) return acc;
    return factorial_tail(n - 1, acc * n);
}

等价循环为：

long long factorial(int n) {
    long long acc = 1;
    while (n > 0) acc *= n--;
    return acc;
}

return n * factorial(n-1) 并不是尾调用，因为递归返回后还要乘以 n。一般递归若无法直接化为递推，就要显式保存系统栈里原本保存的状态；二叉树的非递归遍历和 DFS 都是这种做法。是否消除递归要看可读性、深度上界和实际性能，不能一概而论。

查找

查找表由同一类型的记录构成，每条记录含一个或多个关键字。只查询而不改动的是静态查找表；还要插入、删除的则是动态查找表。衡量查找性能常用平均查找长度（ASL）：

其中 \(p_i\) 是查找第 \(i\) 个记录的概率，\(c_i\) 是所需比较次数。成功和失败查找的 ASL 应分别讨论。

顺序、折半与插值查找

顺序查找从一端逐项比较，不要求记录有序，也适用于链表。成功位置等可能时 ASL 为 \((n+1)/2\)，最坏为 \(n\)。在数组首端设置与待查关键字相同的“哨兵”，可以把循环中的边界判断并入关键字比较。

折半查找要求数据按关键字有序且能随机访问：

BinarySearch(A, key):
    low = 0; high = length(A) - 1
    while low <= high:
        mid = low + (high - low) / 2
        if A[mid] == key: return mid
        if A[mid] < key:  low = mid + 1
        else:             high = mid - 1
    return NOT_FOUND

每次把候选区间缩小约一半，最坏比较次数为 \(\lfloor\log_2 n\rfloor+1\)，时间 \(O(\log n)\)。循环条件必须是 low <= high；更新边界时要越过 mid，否则可能死循环。

插值查找根据关键字在端点值之间的位置估计探测点：

数据近似均匀分布时，插值查找的平均时间可达 \(O(\log\log n)\)；分布偏斜、端点值相同或目标落在值域外时必须作保护，最坏仍会退化为 \(O(n)\)。

索引与分块查找

索引表保存关键字与记录地址的对应关系，用额外空间换取更少的数据访问。顺序索引按一个关键字组织；多重索引为同一批记录建立多套入口。分块查找把记录分成若干块，块间有序、块内可无序：先在块索引中定位，再在目标块内顺序查找。

若共有 \(n\) 条记录、每块 \(s\) 条，约有 \(n/s\) 个索引项。索引顺序查找与块内顺序查找的工作量约为

在 \(s\approx\sqrt n\) 时达到 \(O(\sqrt n)\)；若索引采用折半查找，则约为 \(O(\log(n/s)+s)\)。

索引文件把索引和主文件分开。单关键字索引直接定位记录；多关键字查询可建立多重链表或倒排文件。倒排索引为每个属性值保存包含它的记录地址表，搜索引擎中的“词项 -> 文档列表”就是同样的结构。

二叉搜索树

BST 是动态查找结构，查找、插入均为 \(O(h)\)。它的性能不只取决于元素个数，还取决于形状：平衡时 \(h=O(\log n)\)，退化时 \(h=O(n)\)。详细性质见前文“二叉搜索树”。

散列查找

散列函数 \(h(key)\) 把关键字映射到表地址 \(0,\ldots,M-1\)。不同关键字映射到同一位置称为冲突。好的散列函数应计算简单、覆盖全部关键字，并尽可能把实际输入均匀分散。

课件列出的常用构造方法有：

• 乘法/比例映射：把已知范围内的数线性映射到地址区间，输入接近均匀时效果较好；
• 除留余数法：\(h(k)=k\bmod M\)，通常选择素数或避免带许多小因子的 \(M\)；
• 数字分析法：从已知关键字中选择分布均匀的若干位；
• 平方取中法：对关键字编码平方后取中间若干位；
• 折叠法：把长关键字分段，再移位相加或来回折叠相加。

冲突处理分为两类。

链地址法为每个桶保存链表，同桶元素接在一起。令元素数为 \(N\)、桶数为 \(M\)，装载因子

就是平均链长，可以大于 \(1\)。它容易插入和删除，表接近满时也不会失去可用位置。

开放定址法把全部元素放在表数组里，冲突后沿探测序列寻找空位，因此必须有 \(\alpha<1\)。线性探测

简单且缓存友好，但会产生主聚集。双重散列改用

其中 \(h_2(k)\ne0\) 且应与 \(M\) 互素，才能遍历整张表。开放定址删除时不能直接改成“从未使用”，否则会截断其他关键字的探测链；应留下墓碑标记，或在合适时机重新散列。

散列表的期望查找时间可接近 \(O(1)\)，但这依赖散列函数、冲突策略和受控的装载因子；最坏情况下仍是 \(O(n)\)。当开放定址表过满或墓碑过多时，应扩容并重新散列。

排序

排序按记录关键字重新排列。若相等关键字在排序后仍保持原相对次序，算法就是稳定的。评价排序算法时应同时看比较次数、移动次数、额外空间、稳定性，以及输入是否近乎有序；只报一个 Big-O 不够。

基本排序方法

冒泡排序反复比较相邻逆序对并交换，每一趟把当前最大元素“冒”到末端。若一趟没有交换即可提前结束；最好 \(O(n)\)，平均和最坏 \(O(n^2)\)，原地且稳定。

直接插入排序维护一个有序前缀，把下一个元素向前插到合适位置。输入近乎有序时移动很少，最好 \(O(n)\)；平均、最坏 \(O(n^2)\)，原地且稳定。折半插入可以把寻找位置的比较降到 \(O(n\log n)\)，但元素搬移仍是 \(O(n^2)\)。

Shell 排序按逐渐减小的增量 \(d\) 把序列分组，对每组作插入排序，最后以 \(d=1\) 收尾。较远的逆序能提前消除，实际性能好于普通插入排序；复杂度依赖增量序列，课件不把它归为稳定排序。

简单选择排序每趟从未排序区选出最小元素，与区间首元素交换。无论初始次序如何都要 \(\Theta(n^2)\) 次比较，只作 \(O(n)\) 次交换，原地但不稳定。

快速排序

快速排序选择枢轴，把序列划分为“不大于枢轴”和“不小于枢轴”的两部分，再递归排序两边：

QuickSort(A, lo, hi):
    if lo >= hi: return
    p = Partition(A, lo, hi)
    QuickSort(A, lo, p - 1)
    QuickSort(A, p + 1, hi)

一次划分是 \(\Theta(n)\)。划分较均匀时递推 \(T(n)=2T(n/2)+\Theta(n)\)，得到 \(\Theta(n\log n)\)；若每次枢轴都是极值，则 \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\)。它通常原地、不稳定，递归栈平均 \(O(\log n)\)、最坏 \(O(n)\)。

常用改进包括随机选枢轴、三数取中、把等于枢轴的元素单独分区，以及小区间改用插入排序。先递归较小分区、把较大分区改成循环，还能把栈深控制在 \(O(\log n)\)。

归并排序

归并把两个有序序列在线性时间内合成一个有序序列。自顶向下版本不断二分后回收归并，自底向上版本从长度 \(1\) 的有序段开始，依次合并成长度 \(2,4,8,\ldots\) 的段。

每层归并处理 \(n\) 个元素，共 \(\lceil\log_2n\rceil\) 层，所以最好、平均和最坏时间都是 \(\Theta(n\log n)\)。标准数组实现需要 \(O(n)\) 辅助空间；相等时先取左段元素即可保持稳定。链表归并只需改指针，额外空间可以很小。

堆排序

堆排序先用自底向上方法在 \(O(n)\) 时间内建立最大堆，再反复把堆顶与末元素交换、缩小堆范围并向下堆化。总时间始终为 \(O(n\log n)\)，额外空间 \(O(1)\)，但不稳定。堆的结构与操作见前文“优先级队列与堆”。

比较排序的下界

只依靠关键字比较的排序可表示成一棵决策树。\(n\) 个互异元素有 \(n!\) 种排列，决策树至少要有 \(n!\) 个叶子；高度 \(h\) 的二叉树至多有 \(2^h\) 个叶子，因此

所以比较排序在最坏情况下不可能突破 \(\Omega(n\log n)\)。计数排序等线性时间方法利用了关键字取值范围等额外信息，并不与此下界矛盾。

评论