一些著名问题与算法

　　如果您的飞船破了一个洞，我只能深表同情，因为我所解决的99个问题里唯独没有这个问题。

　　——匿名者1

　　本文提到的所有问题与算法，因为有一些算法仅仅是为了试图说明某个原理，而有一些问题仅仅是为了某个算法而创造的。然而，作为索引，这里会列举出学习中最重要的那些问题与算法。

　　在本文大多数描述中，n代表的是问题规模，如一个序列中的元素数量。而在图论问题中，n表示的是节点的数量，m则表示边的数量。

　　问题部分

　　分团问题与独立集：分团图是每对顶点之间都有边相连的一种图结构。我们对该问题的兴趣主要在于，怎样在一个较大的图中，找到它的分团图（也就是说，分团图实际上是一种子图）。而独立集则指的是图结构中互相没有边与之相连的点。换句话说，找独立集的过程基本等价于将图中每两点之间的连接关系倒转，然后找出该图的分团图。找到一个k-分团图（含有k个节点的分团图），或者找到某图结构中的最大分团图（最大分团图问题），属于NP难题。（更多内容请查阅第11章。）

　　最近点配对问题：在几何平面上给出一些点，找到其中最接近的两个点。它可以在线性对数级时间内，使用分治策略来解决。（见第6章）

　　压缩问题与最佳决策树：哈夫曼树是叶节点有权重的一种树结构。权重与节点深度的乘积和越小越好。这种树结构对于构建压缩编码非常有效，而权重可能是节点已知的概率分布。哈夫曼树可以使用第7章描述的哈夫曼算法（见清单7-1）来构建。

　　连通问题与强连通分量：如果一个无向图的每个节点都可以找到通向其他任意节点的路径，那么我们把这种图结构称为连通图。如果一个基于有向图的无向图是连通的，那么这个有向图也是一个连通图。而连通分量则是图结构中最大的连通子图。连通分量可以用遍历算法来获得，如DFS（见清单5-5）或者BFS（见清单5-9）。另外，如果在一个有向图中，每个节点到其他任何一个节点，都可以找到一条有向路径，那么这个图被称为强连通图。而强连通组件（SCC）则是一幅连通图中最大的强连通子图。SCC可以通过Kosaraju算法（见清单5-10）来找。

　　凸包问题：在几何平面中，凸包指的是包含所有点的最小凸多边形区域。通过分治法，凸包问题可以在线性对数级时间内得到解决（见第6章）。

　　寻找最小值/最大值/中间值：通过单次遍历，我们就可以找到一个序列中的最小值与最大值。通过使用二叉堆，以及线性级时间的准备，我们在常数时间里可以反复提取最大值和最小值。通过随机选择算法，我们也可能在线性级时间（或预期在线性级时间）内，找到一个序列中的第k小的元素。（更多信息请参考第6章。）

　　流量和切割问题：在图结构中，如果每条边上标注了流量，那么其构成的网络总流量应该是多少？这就是最大流量问题。与之等价的一个问题是，找到一组能最大化地限制流量的边。这是最小切割问题。类似的问题存在着数个不同的版本。例如，在边上标注过路费，然后寻找最省钱的路径。或在每条边上标注最小流量，然后寻找可行路径。甚至可以在节点上标注通过该节点的消耗或是要求。第10章讨论了这一系列问题。

　　图着色问题：首先，我们得尝试对图结构中的点进行着色，将每一对直接连接的节点涂成不同的颜色，然后试着对颜色进行分类，尽可能地将着色所用的颜色减到最少。基本上，这是一个NP难题。然而，如果是要判断某一图结构的着色是否可以只用两种颜色（该图是不是个二分图），那么该问题可以在线性级时间内用单次遍历来解决。另外，寻找分团覆盖的问题等价于寻找独立集覆盖问题，它们都与图着色问题非常类似。（关于图着色问题的更多信息，请参见第11章。）

　　停机问题：判定一个给定的算法是否会因某个给定的输入而终止。这通常情况下是一个不可判定（不可解）的问题（见第7章）。

　　哈密顿环路/路径、TSP……和欧拉路径：在路径问题和子图问题中，确实存在着若干个特定问题的高效解决方式。但不意味着一定存在一种方法，可以访问所有的节点，并且每个节点只访问一次。任何有这种限制的问题都被称为NP难题，包括寻找哈密顿环路（从某个节点出发，仅访问每个节点一次并且回到出发节点）、哈密顿路径（从某个节点出发，访问每个节点一次，但不需要回到出发节点），以及寻找完全图的最短路径（旅行商问题）。尽管，无论对于有向图还是无向图来说（见第11章），这些问题都属于NP难题，但它们有一个与之相关的问题：寻找欧拉路径（从某个节点出发，仅访问每条边一次，不需要回到出发节点）则可以在多项式级时间内得到解决（见第5章）。另外，虽然TSP问题仍然是NP难题，但在某些特定情况下，例如您想计算在平面上的几何距离，我们可以将因子规约于1.5之内，然后用其他矩阵距离来解决它。然而，这并不影响其他大多数类似的TSP问题是NP难解的。（更多信息请参见第11章。）

　　背包问题和整数规划：背包问题是一个在某种限制条件下，根据某种边界值摘选某集合子集的问题。在（有限）分数情况下，我们会拥有几种物品，它们各有不同的质量，并且在单位质量上的价值也不尽相同，而我们要将这些物品放入一个背包中。这时候，我们采用的（贪心）解决方案是：从价值最高的物品开始放，尽可能多地放即可。而对于整数背包问题来说，我们必须把一种物品整个放进去，不能仅放入这个物品的几分之几。每种物品都有质量和价值，对于有限制的情况（所谓的0-1背包问题）来说，每种物品都有一定的数量。（另一种同类型的问题是，您有一些固定的物品集合，您可以选择要不要这些集合，但不能拆分任一集合。）而在物品数量不限的情况下，您可以想取多少物品就取多少物品（当然，也要考虑背包容量）。例如，子集和问题就是这种情况的一个特例。它描述了如何从一个数集中取出一个子集，使得子集中元素的和为一个指定的数。这些问题都是NP难题（见第11章），但使用动态规划的话，可以在伪多项式级时间内得到解（见第8章）。而背包问题，甚至可以通过贪心算法，在多项式级时间内解决（见第7章）。整数规划在一定程度上是一般化的背包问题（所以很明显是NP难题）。它只是变量为整数的线性规划问题。

　　最长递增子序列问题：寻找给定的序列中长度最长的递增序列，该问题可以用动态规划（见第8章）在线性对数级时间内解决。

　　匹配问题：匹配问题有很多种，其中最典型的就是对象互相链接的问题。本书中所讨论的问题主要是二分匹配问题、开销最小化的二分匹配问题（见第10章）以及稳定婚配问题（见第7章）。二分匹配问题（或最大化的二分匹配问题）主要涉及的是在一个二分图中寻找边的最大子集，这个子集中不能有两条边的任意两个端点重合。这个问题还有另一个版本：为该图中所有的边标注权值，然后找出权值最大的且符合此条件的子集。稳定婚配问题则与此稍有不同。在该问题中，每个人都会对所有的异性打分，然后根据分数来为他们分配配偶，使得任意两个异性都不会出现宁愿孤独终老也不愿意与对方婚配的情况。

　　最小生成树问题：生成树实际上是一种子图，该子图要是一棵包含其原图所有的节点的树。最小生成树是在边上有权值的情况下，总权值最小的生成树。寻找最小生成树可以用Kruskal算法（见清单7-4）或Prim算法（见清单7-5）。例如，由于边的数量是固定的，最大生成树可以通过取消边的权来找到。

　　分割问题与装箱问题：分割问题指的是将一个数的集合一分为二，使得两个子集的和相等。而装箱问题则是指将一个集合中的数放入若干个“箱子”，使每个箱子内的总数值都不超过某个值，并同时尽可能减少所用的箱子数。这两个问题都属于NP难题。（见第11章）

　　SAT 、Circuit-SAT、k-CNF-SAT：这些都属于可满足性问题（SAT）的变体，它会要求我们给定一个用来判定真值的逻辑（布尔型）公式。当然，前提是我们可以按照自己的意愿设置真值变量。不过，Circuit-SAT问题通常直接应用于逻辑环路中，而不是公式。而k-CNF-SAT问题主要涉及的是公取范式当中的公式。当k=2时，后者可以在多项式级时间内得到解决。而对于k > 2的其他情况，这就是一个NP完全问题了（见第11章）。

　　搜索问题：这是一个非常普遍而又非常重要的问题：通过某个键找到对应的值。这本身就是Python这类动态语言的变量运作方式。在当今互联网世界，这几乎也是寻找所有信息的方式。对此，目前大致上有两种解决方案，即散列表（见第2章）及二分查找/搜索树（见第6章）。而如果数据集中的元素存在概率分布的话，我们也可以用动态语言创建最佳搜索树，以优化查询。

　　序列比对问题：对比两个序列，并找出它们之间相同（或不同）的元素。解决此类问题的方法之一是寻找两个序列中的最长公用子序列，或寻找从一个序列变换到另一个序列所需的最少基本编辑数（Levenshtein distance算法）。这两个问题是等价的。更多信息详见第8章。

　　序列修改问题：向链表中插入元素的时间复杂度非常小（常数级时间），但查找指定元素的时间复杂度却很大（线性级时间）。而对于数组而言，情况则刚好相反（查找时间为常数级，而插入时间为线性级，因为元素插入位置之后的所有元素都需要移动）。但是向两者末端插入元素的时间都非常小（见第2章相关的黑盒子专栏）。

　　集合与顶点覆盖问题：顶点覆盖集是指能够覆盖图中所有的边的顶点集合（每条边至少有一个顶点在顶点覆盖集中）。如果将这个概念中的顶点换为子集，则可以引申出集合覆盖的概念。这个问题的重点在于限制或最小化顶点与子集的数量。这两个问题都是NP难题。（见第11章）

　　最短路径问题：该问题的具体形式包括一个节点到另一个节点之间的最短路径、一个节点前往其他所有节点（反向也可以）的最短路径，以及图中各个节点到其他节点的最短路径。其中，一对一、一对多或多对一的解决方式基本相同。通常使用的是基于未加权图的BFS算法。如果是DAG图的话，则采用DAG最短路径算法，权值非负的情况采用Dijkstra算法，一般情况则采用Bellman–Ford算法。另外，在实践中，为了加快算法的速度（虽然无法提升其最坏情况的运行时间），我们也可以采用双向Dijkstra算法，即A*算法。而对于问题的最后一种情况，可选的算法主要有Floyd–Warshall算法、Johnson算法（适用于稀疏图）。如果边的权为非负值，Johnson算法则（渐近）等价于对每个点使用Dijkstra算法（后者更为高效）。关于最短路径算法的更多信息，见第5章和第9章。另外值得注意的是，（一般图的）最长路径问题通常被用于寻找哈密顿路径。也就是说，这是个NP难题。事实上，这也意味着，对于一般情况而言，最短路径问题也是NP难的。然而，如果我们删去图中的负环，我们的算法即可在多项式级时间内解决问题。

　　排序问题与元素重复性：排序是非常重要的一种操作，也是其他许多算法的基础所在。在Python中，我们一般会借助list.sort()方法或者sorted()函数来完成排序操作，两者都使用了time排序算法的高效实现。其他算法还包括插入排序法、选择排序法及gnome排序法（这些都属于平方级时间的算法）。除此之外，还有堆排序、归并排序及快速排序（这些都属于线性对数级算法，尽管这只是快速排序算法在平均水平下的表现）。关于平方级运行时间的排序算法，更多信息可以参考第5章的相关内容。而对于线性对数级（使用分治法）的算法，我们则可以参考第6章的相关内容。另外，一个实数集是否存在重复值，也直接决定了它的排序时间（在最坏情况下）是否能好于线性对数级。这里需要的是一些归简操作，而不只是排序。

　　拓扑排序问题：将DAG图中的节点按照某种规则排序，使得所有的边指向同样的方向。如果说边代表的是依赖关系，那么拓扑排序就代表了按照这种依赖关系为节点制定的顺序。使用引用计数（见第4章）或DFS（见第5章）可以解决这个问题。

　　遍历问题：该问题主要涉及的是如何在某种连通结构中访问到所有的对象。通常情况下，这个问题都会被表述为图或树结构中的节点遍历。它既可能要求您访问到每个节点，也可能只需要访问其中的某些节点。对于后者，即忽略图或者树结构某一部分的策略，我们通常称之为修剪，往往用于搜索树和分支定界策略中。更多信息请参考第5章。

　　算法与数据结构部分

　　2-3树：平衡树结构，支持插入、删除、搜索操作。这些操作在最坏情况下需要的时间为Θ(lg n)。其内部节点可以有2～3个子节点。并且，该树结构在节点拆分、插入的过程中需要始终保持平衡（见第6章）。

　　A*算法：启发式的单源最短路径算法。它比较适用于大型搜索空间。所以我们不（像Dijkstra算法那样）是根据最短距离值来选择节点的，用的是节点的最低启发值（其等于实际距离值加上剩余距离估计值）。该算法在最坏情况下的运行时间与Dijkstra算法相同。（见清单9-10）

　　AA树：该结构是一棵多层二叉树中的2-3树节点翻转的结果。该算法在最坏情况下插入、删除、搜索的运行时间为Θ(lg n)。（见清单6-6）

　　Bellman–Ford算法：用于找出加权图中某一节点到其他所有节点的最短路径。其查找的途径是沿着每一条边走n次。除非这是一个负向环路，否则其正确答案应该可以在n-1次迭代之后得到确认。如果其在最后一轮迭代中仍有改进的余地，那么它就应该被当成一个负向环路删除掉，并放弃这个运行时间为Θ(ln m)的算法。（见清单9-2）

　　双源Dijkstra算法：在起点和终点同时运行Dijkstra算法，并在这两个算法实例之间交叉迭代。当它们在中间相遇时（虽然这个中间点有些地方值得探讨），最短路径就被找到了。该算法在最坏情况下的运行时间与Dijkstra算法相同。（见清单9-8与清单9-9）

　　二分搜索树：二分搜索树上的每个节点都会有一个键（通常还会有一个对应的值）。并且，经由这些节点的键，我们才能对其子节点的键进行区分。较小的键通常放在左子树中，而较大的则放在右子树中。平均而言，任何节点所在的深度就等于其对数，因而其插入、搜索操作的时间复杂度为Θ(lg n)。如果（像AA树那样）去掉其中的平衡成本，虽然树结构有可能会失去平衡，但可以得到线性级运行时间。（见清单6-2）

　　二分法与二分搜索：一种起源于搜索树的搜索方式。其会在一个已排序的序列中，根据自己的兴趣将序列依次减半。在减半过程中，算法将通过对序列中间元素的检测来决定要偏向左半边还是右半边。该算法的运行时间为Θ(lg n)。Python程序员可以在bisect模块中找到一份非常高效的实现。（见第6章）

　　分支定界法：这是一种通用的算法设计方法。它主要构建一个局部评估方案，然后我们将其作为一个方案空间，用深度优先或最佳优先策略来进行搜索。在此过程中，保守的估值会被当成最佳方案保留下来，而乐观的估值则会被当作局部方案来计算。如果该乐观性估值比保守性估值糟糕，我们就不会扩展该局部方案，同时回溯该算法。这种算法设计通常用于解决NP难题。（见清单11-2，那是一个用分支定界法解决0-1背包问题的范例。）

　　广度优先搜索（BFS）：一种逐层遍历图结构（也可能是树结构），以找出其（不加权的）最短路径的搜索方式。其在实现中将用一个FIFO队列来记录探索到的节点。算法运行时间为Θ(n+m)。（见清单5-9）

　　桶式排序法：该算法所要排序的数值将均匀分布在一组区间内，这些区间都是一些大小尺寸相等的、用于存放相关值的桶。预计这些桶的大小是恒定的，所以它们本身也可以用插入排序法这样的算法来进行排序。算法的整体运行时间为Θ(n)。（见第4章）

　　Busacker–Gowen算法：该算法希望寻找的是一个网络中在最低成本条件下所能达到的最大流量（或该网络在给定流量值下所能做到的最低成本），它采用的是来自Ford–Fulkerson方法中的、最低成本的增广路径。而这些路径的查找则可以通过Bellman–Ford算法或（经过某些加权处理的）Dijkstra算法来解决。在一般情况下，算法的运行时间取决于最大流量值，为伪多项式级时间。如果其最大流量值为k，其运行时间（假设它采用的是Dijkstra算法）就应该为O(km lg n)。（见清单10-5）

　　Christofides算法：主要针对度量型的TSP问题的一种近似算法（近似比大约绑定在1.5），其寻找的是某种最小生成树结构，以及该树奇数节点的最小匹配2，并为相应的图结构构建一个有效的短回路。（见第11章）

　　计数排序法：该算法能在Θ(n)时间内完成对某个小型整数区间（最多能有Θ(n)个连续值）的排序。其工作原理是对出现的数字进行计数，并直接根据该累计值来安排结果中的数字，然后持续更新。（见第4章）

　　DAG的最短路径：寻找某DAG中某个节点到其他所有节点的最短路径。其工作原理是先对节点进行拓扑排序，然后从左至右松弛化每一个节点的所有出向边（或者改成所有入向边也行）。（在无环路的情况下）该算法也可以用来寻找最长路径。运行时间为Θ(n+m)。（见清单8-4）

　　深度优先搜索（DFS）：一种不断深入并回溯图结构（也可能是树结构）的遍历方式。其在实现中将用一个LIFO队列来记录探索到的节点。由于可以对探索及完成时间进行记录，DFS也可以被用来充当其他算法的一个子程序（如拓扑排序、Kosaraju算法等）。算法运行时间为Θ(n+m)。（见清单5-4、清单5-5与清单5-6）

　　Dijkstra算法：该算法可用于寻找某加权图中某一节点前往其他所有节点的最短路径，但前提是图中不能有权值为负的边。它会在遍历图的过程中，不断地通过优先队列（heap）来选取下一个节点。其优先级来自于对节点当前距离的评估值，而这些评估值的更新又来自于当下在已访问节点中找到的短路径。算法的运行时间为Θ((m+n) lg n)。但如果这是一个连通图，时间复杂度就可以简化至Θ(m lg n)。

　　双向队列：FIFO队列通常用链表（或数组的链表）来实现，因此其在任何一段插入与提取对象都可在常数时间内完成。Python程序员可以在collections.deque类中得到一份非常高效的实现。（请参考第5章中相关的黑盒子专栏话题。）

　　动态数组、向量：这是一种让数组拥有额外容量的思路，有助于提高追加元素的操作效率。当该结构被填满时，可以通过某个常数因子扩充成更大的数组。因此在平均水平下，它可以在常数时间内完成追加操作。（见第2章）

　　Edmonds–Karp算法：采用BFS进行遍历的Floyd–Warshall方法实例。该算法可在Θ(nm2)时间内找到相关网络的最低成本流。（见清单10-4）

　　Floyd–Warshall方法：该方法用于寻找图中各个节点前往其他所有节点的最短路径。该算法在第k轮迭代中，沿路只能（按某种顺序）经过前k个中间节点。从第k-1个节点的延伸将取决于其是否能通过最短路径的检查，检查当前从k节点到前k-1个节点的路径是否比直接通往这些节点的路径更短。（也就是k节点是否可被用于最短路径。）算法的运行时间为Θ(n3)。（见清单9-6）

　　Ford–Fulkerson方法：一种最大流问题的通用解决方案。该方法会通过图的重复遍历来找出所谓的增广路径，这是一种会随着流量增长（增广）的路径。而其中的流量又会随着其经过的或所回退的边数（取消访问）而增长，前提是每一条边中都带来额外容量，并且只要经过它们就会产生流量。因此，我们的遍历同时包含了有向边中的前进和回退两种情况，取决于它们共同产生的流量。具体算法的运行时间取决于我们所采用的遍历策略。（见清单10-4）

　　Gale–Shapley算法：该算法致力于对一组男女进行优先排序，然后从中找出稳定的婚配组合。任何一个尚未婚配的男士都会被推荐给一个女士，以作为最佳的婚配对象，而每个女士可以在她当下的追求者中间挑选（其中可能就有她的未婚夫）。算法实现应该在平方级时间内完成这些事。（请参见第7章中“求婚者与稳定婚姻”专栏中的内容。）

　　侏儒排序法：一种简单的平方级排序算法。您在实践中可能不会用到该算法。（见清单3-1）

　　散列操作与散列表：散列是一种通过键值来查找相应值的操作（与搜索树类似）。相关的元素项通常存储在一个数组中，所在的位置将取决于某种（伪随机的或有序的）计算得出的散列键值。只要有一个良好的散列函数和足够的数组空间，散列表的插入、删除以及查询操作都可在Θ(1)时间内完成。（见第2章）

　　堆与堆排序：堆是一种高效的优先级队列。通过某些线性级的预处理，一个最小（或最大）堆可以让我们在常数级时间内查找到结构中最小（或最大）的元素，并且在对数级时间内完成元素的提取或替换。另外，元素的添加也可在对数级时间里完成。从概念上来说，堆实际上是一个完全二叉树结构，树上的每一个节点都小于（或大于）其自身的子节点。当该结构被修改时，修复其属性是一个Θ(lg n)时间的操作。但在实践中，堆通常是用数组来实现的（节点的概念用数组元素的某种编排来表现）。对此，Python程序员可以在heapq模块中找到一份非常高效的实现。Heapsort的执行过程与选择排序法非常类似，只不过它所要排序的是一个堆结构罢了，所以该算法n次查找最大元素的总运行时间为Θ(n lg n)。（请参见第6章的黑盒子专栏“堆结构与heapq、Heapsort”。）

　　哈夫曼算法：该算法用于构建哈夫曼树，以便进而构建出最佳前缀码之用。在初始阶段，算法会将每一个元素（如字母表中的字母）制作成一个单节点的树结构，这时它们的权值等于其出现的频率。然后在每一轮迭代中，都会有两个权值最轻的树被挑选出来，合并成一个新的树结构。该树的权值等于之前两棵树的权值之和。这一切都可以在线性对数级时间内完成（或者说在出现频率已经完成预排序的情况下，它事实上可以在线性级时间内完成）。（见清单7-1）

　　插入排序法：一种简单的平方级运行时间的排序算法。它的工作原理就是反复地向数组中已排序的段落中插入下一个未排序的元素。对于小型数据集来说，这实际上可能是比归并排序法或快速排序法更为优秀（甚至是最佳）的算法。（但在Python中，我们还是应该尽可能地调用list.sort()或sorted()。）（见清单4-3）

　　插值搜索法：该算法与普通的二分搜索法非常类似，但它用来猜测当前位置的是其内部端点之间的内部插值，而不再是简单地查找中间元素。虽然该算法在最坏情况下的运行时间依然是Θ(lg n)，但它在平均水平下，面对分布均匀数据时的运行时间变成了Θ(lg lg n)。（请参见第6章“如果您感兴趣……”一节中所提到的内容。）

　　深度迭代的DFS：该算法会反复地进行DFS，但每次遍历得多远都会有一定的限制。对于某些扇出型结构来说，算法的运行时间与DFS或BFS基本相同（Θ(n+m)）。关键在于它既能发挥出BFS的优势（善于寻找最短路径以及探索大型的固有状态空间），又能像DFS那样具有占用内存少的特点。（见清单5-8）

　　Johnson算法：该算法致力于寻找图中每一个节点前往其他所有节点的最短路径，其基本工作原理就是基于每一个节点运行Dijkstra算法。但该算法在这中间使用了一个技巧，以使得它可用来处理负权值的边。首先，它会在某个（能到达图中所有节点的）新起点上运行Bellman–Ford算法，然后用得到的距离值来修改图中各条边的权值。修改之后，所有边的权值都变成了非负值，但原始图中的最短路径在修改图中依然会是最短路径。算法的运行时间为Θ(mn lg n)。（见清单9-4）

　　Kosaraju算法：该算法致力于通过DFS来寻找强连通分量。首先，卖二手手机平台节点要按照它们的完成时间排好序。然后，反转它们的边，另行运行DFS，按照最先的顺序选择起点。算法运行时间为Θ(n+m)。（见清单5-11）

　　Kruskal算法：该算法致力于通过反复添加不会导致环路的最小剩余来寻找最小生成树。其环路检查可以得到非常有效的执行（当然，这需要一些小聪明），所以算法的运行时间取决于边的顺序。总体而言，大致为Θ(m lg n)。（见清单7-4）

　　链表：一种可替代数组的序列表现结构。虽然在链表中只要找到了元素，修改操作的成本很低（只需常数级时间），但查找本身是一个线性级操作。链表的实现像是一条路径，每一个节点都指向下一个节点，另外需要提醒的是，Python中的list类型是用一个数组来实现的，它并不是一个链表。（见第2章）

　　归并排序法：典型的分治类算法。它在排序时会始终将序列从中间分开，然后继续对那两半部分进行递归，最后在线性时间内将排序好的那两半合并起来。算法的总运行时间应为Θ(n lg n)。（见清单6-5）

　　Ore算法：人们通过标记通道入口与出口来遍历实体迷宫的一种算法。其在多数情况下类似于基于深度迭代的DFS或BFS。（见第5章）

　　Prim算法：该算法致力于通过反复添加与树最接近的节点来使其成长为一棵最小生成树。其核心部分与Dijkstra算法类似，由一个遍历算法与一个优先级队列组合而成。（见清单7-5）

　　基数排序法：该算法将从最低有效位起，通过（元素的）数位来对数字序列（或其他类型的序列）进行排序。只要数位的个数是恒定的，并且数位能在线性时间完成排序（如通过计数排序法），算法的总运行时间应为线性级。该排序算法的侧重点基于数位的稳定性。（见第4章）

　　随机选取法：该算法致力于查找中间数，或者通常情况下的第k顺位的某个数（第k小的元素）。其工作原理就像是“半个快速排序法”。它会随机（或者说任意）选择一个分割点元素，将其余元素划分到它的左边（更小的元素）或右边（更大的元素）。然后在各部分继续搜索，整个过程或多或少与二分搜索有些类似。完美平分虽不能保证，但预计的运行时间依然是线性级的。（见清单6-3）

　　选取法：虽然相当不现实，但该算法确实可以保证在线性级时间内对兄弟节点进行随机选取。其工作原理如下：先将目标序列划分成五个组，然后分别用插入排序法找到它们各自的中间值，接着用选取法递归地找出这五个中间值中的中间值，再以该中间值的中间值为分割点划分元素。现在，我们就可以在合适的那一半元素上进行选取了。换言之，它与随机选取很相似——不同之处在于，现在我们可以确保分割点两侧存在着一定的比例关系，避免了完全不平衡的情况。这不是一个我们实践中真正会的算法，但了解它依然有着重要的意义。（见第6章）

　　选择排序法：一种简单的平方级排序算法。它的工作原理与插入排序法非常类似，只不过这回不是将下一个元素插入到已排序的区段中，而是找出（选取）未排序区段中最大的那个元素（并交换它与最后一个未排序元素的位置）。（见清单4-4）

　　Tim排序法：这是一种非常棒的、基于归并排序法的就地型排序算法。除了一些被明确声明条件的、未经处理的特殊情况外，它甚至能对已排序的序列做出针对性处理，包括那些反序的序列段。因此，它对某些真实世界中的序列来说，排序速度可能要比通常的情况更快一些。其在list.sort()与sorted()的实现中也确实很快，所以您会需要用到它们。（请参考第6章黑盒子专栏“Tim排序法”中的相关内容。）

　　基于引用计数的拓扑排序法：该算法用于对DAG的节点进行排序，使其所有边呈现从左向右的形态。整个过程将通过对每个节点的入向边计数来完成。入向边数为0的节点将会被保存到一个队列（也可以只是一个集合，顺序无关紧要）中。这些节点将从该队列中被取出，并放入拓扑排序的顺序当中。当我们这样做时，我们就是在递减相关节点入向边的计数。当它们减到0的时候，就可以放到队列中去了。（见第4章）

　　基于DFS的拓扑排序法：另一种用DAG拓扑排序的算法。该算法的思路很简单，即执行DFS，然后在完成时反转节点的顺序。另外，如果想更轻易取得线性级的运行时间，我们也可以直接在DFS的过程中，在每个节点完成遍历时就将其添加到结果顺序中。（见清单5-7）

　　Tremaux算法：与Ore算法一样，这是一种为让人们能步行穿越迷宫而设计的算法。在该算法执行过程中，人们所用的跟踪模式其实基本上就等同于DFS。（见第5章）

　　绕树两周算法：一种针对公制TSP问题的近似算法，它可以确保我们得到解决方案的成本最多是最佳方案的两倍。首先，它会构建一棵最小生成树（它的成本小于最佳方案），然后它会在该树上“绕行”，并且走捷径以避免重复访问相同的边。由于采用公制的原因，它可以确保自己的操作成本低于每条边被访问两次的成本。至于最后一次的遍历，则只需用现成的DFS来实现即可。（见清单11-1）