【高级数据结构与算法分析】课程笔记

· · 算法·理论

成绩：96/100，绩点 5.0

希望能以尽量简洁的方式对 ads 的各个知识点做一个梳理

AVL Tree

定义：对一棵二叉搜索树，如果每个节点都满足：左右子树高度相差不超过 1，则这棵树就是一个 AVL 树

那么显然高度为 h 的 AVL 树的节点数至少是斐波那契数，故树高还是 O(\log size) 的

插入

从根节点往下递归，根据当前节点元素和插入元素的大小关系决定向左子树还是向右子树递归

最后递归至空节点，此时完成插入操作

删除

性质维护

由于插入和删除至多只会造成高度差 =2 的问题，因此关注违反性质的两层节点：

一共有四种情况，这里只列出来两种，另外两种旋转模式是对称的

Splay Tree

Splay 与 AVL 非常类似，但是它不需要维护子树高度，而是只通过旋转来保证 O(\log n) 的单次均摊复杂度

这个复杂度的含义为：从空树开始的任意 m 次连续的操作所需的时间为 O(m\log n)，其中 n 为树的大小

注意这里只说了 m 次操作的总时间，因此单次操作的复杂度开销可能很高（例如访问一个深度很大的节点），因此无论何时，在访问到一个节点之后，都需要将其旋转至根

旋转操作：Splay

设当前节点为 u，父节点为 x，祖父节点为 y（如果存在的话）

插入操作

按正常 BST 插入流程操作，插入完成之后将这个节点 splay 至根

删除操作

先找到待删除节点，将其 splay 至根，然后：

Inverted File Index

似乎只考这个东西：

Relevant Irrelevant
Retrieved R_R I_R
Not Retrieved R_N I_N

然后得到：

Leftist Heaps

除了插入/删除堆顶，我们还希望能够做到快速合并两个堆，从而引出了左偏堆这种结构

定义：记节点 x 的空路径 Null path length（Npl）为到其子树内最近一个少于两个儿子的节点的距离，特别地，定义 Npl(NULL)=-1

性质：显然，\operatorname{Npl}(x)=\min(\operatorname{Npl}(ls(x)),\operatorname{Npl}(rs(x)))+1

那么左偏堆满足：

  1. 堆序：即若为小根堆，则父节点元素不大于子节点元素
  2. 对每个节点 x，有 \operatorname{Npl}(ls(x))\ge \operatorname{Npl}(rs(x))

性质：

因此，如果可以将所有操作和最右链的长度挂钩，那么就可能做到较好的复杂度

合并操作

（下文以小根堆为例，另外，插入操作相当于合并一个单点，故略去不谈）

递归版本

假设目前需要合并以 H_1,H_2 为根的两个左偏堆：

这样合并的复杂度为两个堆的最右链长度之和，即 O(\log size)（这个复杂度是严格的）

迭代版本

将两个左偏堆的最右链拿出来归并形成一条新的最右链，同时保持最右链上每个节点的左儿子不变

归并完之后，从下往上调整左右儿子是否交换，以及更新 \operatorname{Npl} 即可

在手动模拟的时候会方便很多

删除操作

弹出堆顶，相当于合并根节点的左右子树，显然左右子树依然是左偏堆

Skew Heaps

斜堆和左偏堆的关系非常类似于 Splay 和 AVL 之间的关系，不再关心 Npl

合并操作

依旧以小根堆为例

递归版本

假设目前需要合并以 H_1,H_2 为根的两个斜堆：

迭代版本

将两个斜堆的最右链拿出来，将这些点中每个点的左儿子交换到右侧，然后将这些点归并形成一条新的最左链

在手动模拟的时候会方便一点

复杂度分析

与 Splay 类似，斜堆的复杂度分析也需要在均摊意义下进行，同时由于插入和删除都是合并的特殊情形，因此只关注合并

定义：称一个节点 x 是重节点（Heavy Node）当且仅当 x 的右子树大小大于等于 x 的左子树大小，若不满足，则称 x 是轻节点（Light Node）

那么定义一个局面 D 的势能函数 \Phi(D) 为当前局面中重节点的个数

然后分析合并操作的均摊代价：

  1. 实际代价 T_w=h_1+l_1+h_2+l_2 为两个斜堆的最右链长度之和
  2. 势能变化量（非最右链的节点轻重性质不变，设这部分节点中重节点个数为 H）
    • \Phi_1=h_1+h_2+H
  3. 因此均摊代价 T_a=T_w+\Phi_2-\Phi_1\le 2(l_1+l_2)=O(\log n)（最右链上轻节点个数 \le \log n，因为从下往上每经过一个轻节点子树大小至少翻倍

Backtracking

原理：穷举所有的可能性，并剪枝（pruning）一部分无需搜索的内容

Eight Queens

著名的八皇后问题，在 8\times 8 的棋盘上放置 8 个皇后，满足任意两个皇后都无法彼此攻击

暴搜做法非常简单，按行新加一个皇后之后，判一下与之前的皇后在斜向及竖向是否会攻击到即可

注意：n 皇后问题的解空间大小为 n!（即需要检查 n! 个可能的解）

搜索树：将暴搜的过程用树形结构表示出来，从而剪枝就代表了舍弃一个子树不往里面递归

Turnpike Reconstruction Problem

问题：

数轴上有 n 个未知的点 x_1,x_2,\cdots,x_n，已知 0=x_1<x_2<\cdots<x_n，和 n 个点两两距离（共 n(n-1)/2 个距离）

构造出任意一组满足条件的点集

例如：

给出距离集合 D=\{1,2,2,2,3,3,3,4,5,5,5,6,7,8,10\}，那么通过 |D|=15 可知 n=6

（可以给出这个做法的时间复杂度的上界为 O(2^nn^2)，但实际运行情况可能会比较好）

Tic-tac-toe（井字棋）

广为人知的一个游戏

对于这类问题，实际上是有两个玩家在进行博弈，因此会有类似 \min-\max 搜索的效果

Minimax Strategy

定义 W_A,W_B 分别为当前局面下玩家 A,B 能获得胜利的方案数，例如：

* A *
* B *
* * *

此时就有 W_A=4,W_B=6

A A A  A A *  * A A  * A *  |  B A *  * A B  * A *  B A *  * A B  * A *
* B *  A B *  * B A  * B *  |  * B *  * B *  B B B  B B *  * B B  * B *
* * *  A * *  * * A  A A A  |  * * B  B * *  * * *  B * *  * * B  B B B

那么定义局面的的 W 值为 W_A-W_B，那么显然先手会最大化 W，后手会最小化 W，体现在搜索树上，就是一层取子节点最大值，一层取子节点最小值，两种状态交替进行

\alpha-\beta pruning

上图中，已经搜索完 44 对应的子树和 40 对应的子树，那么可以知道：

那么就可以判定，黑色节点无论取值多少，都无法影响到根节点的值了，那么此时就可以剪掉这部分搜索

同理还有这种情况，黑色节点部分也不需要再进行搜索了

NP-Completeness

这一章将讨论一些非常困难的问题，先举几个例子：

说这些问题困难，是因为这些问题目前还没有多项式时间的确定性算法

什么是算法？

定义：算法是解决某个问题的一系列步骤，接受（也可以没有）输入，产生输出（必须有），同时每一步必须是良定义的，同时整个算法过程可以在有限的时间内结束

不可判定问题（Undecidable Problems）

哥德尔证明了任何公理系统都是不完备的，换言之，不存在一套理论能证明所有命题

最著名的不可判定问题是图灵停机问题（Halting Problem）：

另一个不可判定问题是 Post Correspondence Problem：

两种图灵机（Turning Machine）

确定性图灵机（Deterministic Turing Machine）

每一步执行一条指令，并跳转至下一条指令

非确定性图灵机（Nondeterministic Turing Machine）

每一步执行一条指令，并跳转至集合中的任意一条指令中，若其中某一条指令能得到解，那么一定会选择这条指令

NP: Nondeterministic Polynomial-time

称一个问题是 NP 的，当且仅当这个问题可以在多项式时间内被非确定性图灵机解决（这里的多项式时间，指的是与输入量形成多项式关系）

换言之，如果可以再多项式时间内验证任意一个解的正确性，那么这个问题就是 NP 的

例如：哈密尔顿回路问题是 NP 的，因为很容易验证一个解是不是一个哈密尔顿圈

类似地，P: Deterministic Polynomial-time

两类问题的关系

显然 P\sube NP，但是是否有 P\sub NP 呢？目前仍然不知道

NPC: NP-Complete

这是所有 NP 问题中最难的一类，其中的最难，指的是如果解决了任意一个 NPC 问题，那么就能解决所有的 NP 问题（所有 NP 问题都能多项式时间规约到 NPC 问题）

换言之，所有的 NP 问题都是 NPC 问题的弱化版，得到了 NPC 问题的一个解，就能多项式时间得到到 NP 问题的一个解，同时所有 NPC 问题都是一样难的

第一个 NPC 问题

历史上第一个被证明 NPC 的问题是电路可满足性问题（Satisfiability Problem），即给出一个包含若干布尔变量的布尔表达式，问是否存在一种设置变量的方式，使得表达式的结果为真

（解决了这个问题，就能解决所有的 NP 问题）

一个例子

假设我们已经知道哈密尔顿回路问题是 NPC 的，那么如何导出 TSP 问题（给出一张带权完全图和参数 K，问是否存在一个哈密尔顿回路边权之和 \le K）也是 NPC 的

NPH: NP-Hard

这类问题至少和 NPC 问题一样难，但是 NP-Hard 问题可能是无法在多项式时间内判定解的正确性的（因此可能会更难）

结论：NPC=NP\cap NPH

一个例子

TSP 问题的优化版本（即求最小权哈密尔顿回路）就是 NPH 的，因为无法在多项式时间内验证这个解是 “最优” 的

Approximation Algorithms

一般来说，解决问题需要考虑三个方面：

近似算法用于解决一些非常困难的问题（例如 NPC 问题），这种问题的处理办法通常有：

近似比

称一个算法对规模为 n 的数据有 \rho(n) 的近似比（approximation ratio，换言之，该算法是 \rho(n) 近似算法），当且仅当对任意数据：

近似方案

一个近似方案（approximation scheme）同时以一组数据和一个参数 \varepsilon 为输入，满足当前算法是 (1+\varepsilon) 近似的

Polynomial-time approximation scheme（PTAS）

如果一个近似方案对任意固定的正数 \varepsilon 都能在多项式时间内运行，则称其是一个 PTAS（多项式时间近似方案）

（这里，固定的正数表示我们不把 \varepsilon 当做变量，换言之，出现类似 O(n^{1/\varepsilon}) 的复杂度是接受的）

另外，还有全多项式时间近似方案（Fully polynomial-time approximation scheme, F-PTAS），如果算法的运行时间关于 n 和 1/\varepsilon 都是多项式（例如 O((1/\varepsilon)^2n^3) 之类的）

Bin Packing Problem

问题：

给出 n 个物品，每个物品用其大小 s_i 描述，先有无穷多个大小为 1 的背包，问至少需要多少个背包可以装下所有物品

（这个问题是 NP-Hard 的，因为无法验证是否能用 K 个背包装下所有物品；但是它的判定版本是 NPC 的，因为给出一组分配方式之后，可以很容易得到背包个数是否 \le K）

接下来介绍两种不同的近似方法：

Next Fit

这个做法的近似比为 2，进一步地，如果最优解为 M，则这个做法得到的结果 \le 2M-1，同时这个上界是紧的（可以被构造到的）而它的证明也是容易的：

考虑反证，即最优解为 M，且这个做法得到的结果为 2M，那么设 W(i) 表示在这个做法中第 i 个背包装的物品总重量

于是可以得到 n 个物品的总重量 T：

\begin{cases} W(1)+W(2)>1\\ W(3)+W(4)>1\\ \cdots\\ W(2M-1)+W(2M)>1 \end{cases}\Rightarrow T=W(1)+W(2)+\cdots+W(2M)>M

从而无论如何都需要至少 \lceil T\rceil=M+1 个背包才能装下，矛盾

First Fit

这个做法的近似比为 1.7，同时这个上界是紧的

一个改进版本（First Fit Decreasing, FFD）为：在一开始将所有物品按照重量降序排序，然后做正常的 First Fit，这个做法的近似比为 11/9，同时这个上界是紧的

Best Fit

这个做法的近似比也为 1.7

Online Algorithm

对于在线问题，每次输入一个物品，然后需要立即回答将这个物品放入之前哪个背包中，或是新开一个背包

那么上面的做法中，NF，FF，BF 都是可以在线化的，FFD 不能在线化

同时：任何在线算法的近似比都无法低于 5/3，除非 P=NP

Knapsack Problem

分数背包（fractional version）

问题：假如每种物品以重量 w_i，单价 p_i 来描述，且物品可以被任意切分成一定重量，在这种情况下装入大小为 W 的背包能得到的最大价值

这个问题是比较容易的，按照单价 p_i 从大到小贪心取物品能放就放即可

01 背包（0-1 version）

问题：假如每种物品以重量 w_i，价值 p_i 来描述，物品无法切开，在这种情况下装入大小为 W 的背包能得到的最大价值

有两种策略：

然后取两种策略得到的结果的较大值，那么这个算法的近似比为 2（好像没有证明）

另外，如果使用动态规划，那么可以在 O(n\sum w_i) 的时间内求出精确解（注意，这并非多项式时间复杂度，因为 w_i 一项关于输入量不是多项式的）

K-center Problem

问题：给出平面上的 n 个点 p_i，确定 k 个中心点 q_i，使得所有点到最近中心点欧几里得距离的最大值最小

换言之，最小化：

\max_{i=1}^n\{\min_{j=1}^k\{\operatorname{distance}(p_i,q_j)\}\}

（这里，距离指的是欧几里得距离，满足对称性，自反性和三角不等式，具有同样性质的距离还有曼哈顿距离）

一个简单版本

这个问题较为困难，不妨先考虑这个版本：

实际上是可以的，如下算法即是：

  1. 取出点集中的任意一个点，将这个点作为一个中心点
  2. 以这个点为圆心，2r 为半径作圆，删除圆内的所有点
  3. 回到第一步，不断重复直到点集被删空

这样构造出的中心点个数一定不超过 k（解释一下，最优解的一个圆中任意两个点距离 \le 2r，因此如果一对点在最优解中处于同一个圆中，那么在上面的构造中这一对点也一定可以出现在同一个圆中（只是可以而非一定），从而不可能需要多于 k 个中心点）

从而，如果按照上面的做法构造出多于 k 个中心点了，那么最优解一定 >r（逆否命题）

回到原问题

回顾上面的做法，实际上第二步取点这里是与 r 有关的，那么能否每次取一个最远的点呢，这样每一步都能 “取到更远的地方，从而一次删掉更多点”，那么修改一下上述做法，把 r 这部分去掉：

  1. 取出点集中的任意一个点，把这个点作为第一个中心点
  2. 接下来，每次取出与所有中心点最近距离的最大的那个点，将这个点加入中心点集
  3. 不断重复操作，直至取出 k 个中心点
  4. 构造出所有中心点之后，得到半径 r'，则有 r'\le 2r，即这个算法的近似比为 2

可以发现这里的第二步与上面做法的第二步起到了同一个效果

这个问题有多难

这个问题没有低于 2 的近似比的做法，除非 P=NP（证明的话，已经证明了如果存在 (2-\varepsilon) 近似，则可以在多项式时间内解决支配集问题）

另外，如果距离定义不满足三角不等式（非度量 k-center 问题），则这个问题甚至不存在任意常数近似比的做法，除非 P=NP，不可改进界为 o(\log n)

Local Search

从直觉上理解局部搜索，其实就相当于梯度下降，在一个碗里让小球按重力作用下滑，那么最终小球静止的位置就是一个局部最小值

那么对算法也是如此，每次对当前解做出一个微小的扰动，并选择最优的那个方向递归下去，直到成为邻域中的最优解，此时找到了局部最优解，算法停止（由于局部最优解不一定是全局最优解，因此局部搜索也是近似算法）

Vertex Cover Problem

顶点覆盖问题：给出一张 n 个点 m 条边的无向图，求出一个最小的点集 S，满足任意一条边都有至少一个端点在 S 中

那么需要界定的内容有：

因此就可以得到一个（实际上很蠢）的做法：

一些改进

Hopfield Neural Networks

问题：给出 n 个点 m 条边的带权无向图，边权 w_e 为正或为负，需要给每个节点设置一个 1/-1 状态，若 w_e>0 则表示希望两端点状态相反，否则表示希望状态相同

由于满足所有边权的限制可能无法做到（若将 w_e<0 的边缩起来之后存在奇环就无解），因此希望找到一个尽量好的解

一个新的问题：

那么一个简单的做法：

这个做法能在有限步内结束吗？可以，这个算法会在至多 \sum|w_e| 步之后结束：

设势函数 \Phi(S) 表示当前局面下所有好的边的边权绝对值之和

那么在翻转一个不好的节点的状态之后：

如果将上面的分析应用到局部搜索中，就是每次翻转一个状态，最大化最终状态的 \Phi(S)

The Maximum Cut Problem

最大割问题：给出 n 个点 m 条边的带权无向图，将点集分成两个部分，最大化横跨两个部分的边权之和

（最小割问题是容易问题，因为最小割等于最大流）

将每条边的边权都取反，那么一个割的权值就是 \Phi(S)，那么上一个问题的做法自然可以应用到最大割问题

解有多好？

这个局部搜索算法的近似比为 2，证明如下：

设 A,B 为该算法分出来的两个点集，w(A,B) 为割的权值，由于得到的是一个局部最优解，因此对每个 u\in A，都有：

\sum_{e=(u,v),v\in A}w_e\le \sum_{e=(u,v),v\in B}w_e

那么：

w(A,B)=\sum_{u\in A}\sum_{v\in B}w_{uv}\le \sum_{u\in A}\sum_{v\in A}w_{uv}=2\sum_{\{u,v\}\sube A}w_{u,v}

同理可得 w(A,B)\le 2\sum_{\{u,v\}\sube B}w_{uv}

那么最优解 (A^*,B^*) 就有：

w(A^*,B^*)\le \sum_{e}w_e=\sum_{\{u,v\}\sube A}w_{uv}+\sum_{\{u,v\}\sube B}w_{uv}+w(A,B)\le 2w(A,B)

于是得到近似比为 2

另外：

能做到多快？

如果一次扰动能做到比较大的改进才接受：如果一次扰动让答案至少增大了

\dfrac{2\varepsilon}{|V|}w(A,B)

那么才接受，在这种做法下，可以做到 (2+\varepsilon) 的近似比，同时算法会在至多 O(\dfrac{n}{\varepsilon}\log W) 步后结束

更大的邻域？

可能在一次扰动翻转多个节点的状态

Randomized Algorithms

随机的对象是？

Hiring Problem

问题：

有 n 个面试者，用能力值 a_i 描述，先希望从 n 个面试者中雇佣 1 位

其中，面试成本为 C_I，雇佣成本为 C_H，且 C_I 远小于 C_H

现在希望平衡总成本与雇佣到的面试者的能力

一个最直接的做法
  1. 按顺序面试所有人，并维护目前能力值最大值
  2. 在新来了一个人后：
    • 若其能力值大于目前最大值，则雇佣（之前那个被自动解雇了）
    • 否则，不雇佣

这个做法的有点在于一定能雇佣到能力值最大的人，但是总成本在 a_i 单增的情况下最坏可以达到 O(nC_H)（C_I 一项忽略了）这是不可接受的

如果将面试顺序打乱？

考虑 n 个人随机重排之后使用上面的做法，那么成本分成两个部分：

现在只需要计算 m 的期望，同时由线性性，m 的期望可以转化为每个人被选中的期望，这里 n 个人进行了随机重排，那么位于位置 i 的人被选中（即其为 1\sim i 中的最大值）的概率为 \dfrac{1}{i}，于是

E(m)=\sum_{i=1}^n\dfrac{1}{i}=\ln n+O(1)

最终总成本为 O(nC_I+\ln n\cdot C_H)，也能雇佣到能力最强的人，同时期望成本大大降低（最坏情况还是很差（即随机到单增序列这种逆天情况），但是几乎不发生）

Online Hiring Problem

内容同上，但是这里只能雇佣一次（在这种情况下，总成本不考虑，只考虑雇佣到的人的能力）

此时我们的做法是将所有人先随机重排，然后取前 k 个人的最大值 A，再遍历后面 n-k 个人，雇佣第一个遇到的 \ge A 的人即可

然后需要分析 k 的取值，即雇佣到最大值的概率

设雇佣到了位置 i，且其确实是最大值的概率为 P(i)，那么有两个条件：

那么雇佣最大值的概率为

\sum_{i=k+1}^nP(i)\approx \dfrac{k}{n}\ln \dfrac{n}{k}

对 k 求极值，得到 k=n/e，此时概率为 1/e 是最大值

Quicksort

确定性快速排序：

引入随机化思想，每次随机一个 pivot

定义 Central splitter：若一个 pivot 将规模为 n 的原问题分为两半，其中每一半都至少是 n/4，则成这个 pivot 是一个 central splitter

那么显然有一半的数字都是 central splitter，因此期望递归两层就能找到，一旦找到，最坏情况也是分为 n/4 与 3n/4 的两个部分，在取对数意义下时间复杂度依然是 \Theta (n\log n)

Parallel Algorithms

背景：有多个处理器可以同时运行，同时对一个共享的数据空间进行读写

那么在资源上可能产生冲突，于是出现了以下几种模式：

Summation Problem

按照线段树的方式执行求和，一层一层往上做，每一层中的所有加法并行执行

其中 B(h,i) 为线段树节点编号，h 为节点所在深度，叶子为 0，向上递增，i 为同层编号，从左往右从 1 开始

那么显然 B(h,i)=B(h-1,2i-1)+B(h-1,2i)，且 B(0,i)=A(i)

衡量处理器数量与运行时间的方式

定义：

那么显然：T_1=W,T_\infty=D，对于处于中间值的 p，其 T_p 往往较难分析（与具体算法有关），但有以下关系：

\dfrac{W}{p}\le T_p\le \dfrac{W}{p}+D

（粗略理解就是将整个算法执行的单位操作拓扑排序，然后按 p 个一组来做，这样一共要做 W/p 轮，其中每一层由于上取整会多出来一个不满 p 个的组产生额外 1 的贡献，因此下界与上界差了 D）

回到 Summation Problem，对上面的做法，就有 W=\Theta(n),D=\Theta(\log n)

Prefix-Sums

问题：给出序列 A(1),A(2),\cdots ,A(n)，计算所有前缀和 C(i)=A(1)+A(2)+\cdots +A(i)

那么设：

于是在合并两棵子树 (h-1,2i-1),(h-1,2i) 时：

初始情况为 B(0,i)=C(0,i)=A(i)，显然每一层的处理都可以并行做

这样 W=\Theta(n),D=\Theta(\log n)

归并

问题：给出两个有序的序列 A(1\cdots n),B(1\cdots n)，希望将它们合并成一个有序的序列 C(1\cdots 2n)（这里假设 A(i),B(i) 两两不同，若不满足，则可以额外添加一维关键字）

传统归并必须按顺序比较 A,B 中的数字，几乎无法并行，因此从另一个方向入手：找到 A(i),B(i) 合并后的排名

设 rk(A,i) 为 B 中比 A(i) 小的数字个数，rk(B,i) 同理

那么合并过程即为：

for i=1 to n pardo
    C(i+rk(A,i)):=A(i)
for i=1 to n pardo
    C(i+rk(B,i)):=B(i)

现在考虑能否并行解决排名求解问题

Parallel Ranking

两个最直接的做法
  1. 按照传统方式求 rk，此时相当于按传统方式归并，因此 W=D=\Theta(n)
  2. 并行执行 n 次二分查找，此时 W=O(n\log n),D=O(\log n)
Partitioning

Maximum Finding

问题：求出 n 个数的最大值

两个最直接的做法

  1. 显然这个东西可以复用 Summation Problem 的做法，把所有的加法操作换成 \max 即可，这样不难做到 W=O(n),D=O(\log n)，但是这种做法忽略了一个性质：\max 运算允许内容重叠但加法不允许

  2. 并行所有 \operatorname{pair}(i,j) 的大小比较，然后并行检查每个数是否存在比它大的数，这样 W=O(n^2),D=O(1)

    • 解释一下，这里当 A(i)<A(j) 时将 B(i) 置 1，这里可能存在同时写入的情况，但是是允许的（Common rule，写入的值都是 1）
稍微优化一下

将 A(1\cdots n) 划分为 \sqrt n 个部分，每个部分包含 \sqrt n 个数，然后应用上面的做法，这样

这样就稍微优化了一下上面的做法

再稍微优化一下（Doubly-logarithmic Paradigm）

做两步：

于是 h 取 \log\log n，就可以做到：T(n)=O(\log\log n),W(n)=O(n)

一个随机化做法（Random Sampling）

在期望意义下表现非常好，分成以下几步：

  1. 从序列 A 中随机取出 n^{7/8} 个数形成序列 B
  2. 将序列 B 划分为 n^{3/4} 个部分，每个部分包含 n^{1/8} 个数，然后对每个部分使用 W=O(n^2),D=O(1) 的做法，则总共为：W=n^{3/4}\times (n^{1/8})^2=O(n),D=O(1)
  3. 这样序列 B 长度就缩小为 O(n^{3/4}) 了，将 B 划分为 n^{1/2} 个部分，每个部分包含 n^{1/4} 个数，对每个部分使用同样的做法，总共为 W=n^{1/2}\times(n^{1/4})^2=O(n),D=O(1)，于是就找到了 B 中的最大值 M
  4. 接着暴力遍历 A 中没有放入 B 的数，如果存在数 >M，则将所有这些数字随机替换掉序列 B 中的数，并回到第二步重新做一轮，直到不存在数 >M 为止

可以证明，每一轮均为 W=O(n),D=O(1)，同时期望轮数是常数，因此最终为 W=O(n),D=O(1)

External Sorting

背景：

定义

Record：单个数据

Run：有序段（即一系列已排好序的数据）

Tape：磁带（即若干分立的存储空间）

Pass：归并排序的总轮数

设总数据规模为 n，内存能容纳的数据规模为 m

一个最简单的做法（两路归并，4-tape）

  1. 所有数据初始存储于 T_1 磁带中，然后以 m 个一组载入内存中，用任意其他排序算法在内存中排好序，形成一个 run，并以 2,3,2,3\cdots 的顺序加入到其他 tape 中
  2. 接下来每一轮，每次取出所有 tape 的第一个 run 进行归并，形成一个更长的 run，并用与上相同的方式加入到空闲的 tape 中，知道只剩下一个 run，此时排序完成

其中第 1 步也算一个 pass，那么第 1 步结束后有 n/m 个 run，第二步每一轮 pass 完成后单个 tape 上的 run 个数减半

因此总 pass 轮数为 1+\lceil \log_2(n/m)\rceil

优化：k 路归并

但是直接按照上面的方式，需要 2k 个 tape，继续优化

考虑按照斐波那契数列对所有 run 进行划分：

 0  0 34 (split 34 to 21+13)
21 13  0 (13 run from 1,2 to 3)
 8  0 13 ( 8 run from 1,3 to 2)
 0  8  5 ( 5 run from 2,3 to 1)
 5  3  0 ( 3 run from 1,2 to 3)
 2  0  3 ( 2 run from 1,3 to 2)
 0  2  1 ( 1 run from 2,3 to 1)
 1  1  0 ( 1 run from 1,2 to 3)
 0  0  1 (finish)

这样就用 3 个 tape 完成了 2 路归并（如果初始 run 个数不是斐波那契数则补到最近的）

那么 k 路归并就只需要使用高阶的斐波那契数列即可

F_n^{(k)}=\sum_{i=1}^kF_{n-i}^{(k)}

同时只需要使用 k+1 个 tape

优化：并行

结论：如果要并行进行 k 路归并，则需要将内存划分为 2k 个输入缓冲区和 2 个输出缓冲区

（大意可能是一半处理一半输入/输出，这样同时进行）

优化：生成更长的 run

容易想到，如果初始 run 长度 \ge m，那么 run 个数就会少，pass 也会减小，那么采用 replacement selection 算法：

在序列初始已经基本有序的情况下，这种方法往往非常有效

（相当于维护了两个堆，一个堆存储能放在同一个 run 里的，另一个存储不能的，每次取出第一个堆的堆顶，然后加入一个数就看一下大小关系来确定放在哪个堆里，当第一个堆弹空了就新开一个 run，并交换一下两个堆）

优化：缩短合并时间

对 k 路归并，使用哈夫曼编码的方式进行合并（每次合并最短的两个 run）