每个程序员都必须知道的（类）算法

在《末日隧道》中，我写道不相交集算法是每个程序员都应该知道的极少数算法之一。这让我思考。应该？必须的呢？如果每个人都必须了解不相交集，那么每个程序员还必须了解哪些其他算法？我列出了每个程序员都必须知道的算法和数据结构的“前十名”列表。列表、数组、堆栈。列表、数组和堆栈当然是最基本的数据结构，但是，这些构建块可以保留一些惊喜。例如，在 STL 中广泛使用违反直觉的哨兵节点来表示刚刚通过列表中最后一个元素的位置。例如，这使得在 end() 位置插入一个项目相当有效。虽然列表不允许直接访问元素，但数组可以，但代价是分配已知的先验内存量。相反，在给定当前位置的情况下，将元素插入列表是常数时间，而在数组中插入新元素的成本更高，这取决于是否要保留排序。可以说，堆栈是两者的一种特例，因为它们的行为大多类似于列表，其中只允许在一端进行操作；并且喜欢数组，因为它们通常在连续的内存范围内实现，即数组。由于这三个是更复杂的算法和数据结构的常见构建块，因此您应该真正掌握它们。树木。树，或者更准确地说是搜索树，无论它们是二元、k-ary、splay、AVL 还是 B，都是列表中的下一个数据结构，提供搜索、插入和删除值的操作（在一般情况下）。最有趣的树品种试图确保它们在 中也有更坏的情况，也就是说，它们不会走得太深或花费过多的时间来执行它们的操作。为此，流行的策略是平衡树，使其在任何地方（几乎）具有相同的深度。有些品种的分枝因子远高于 2，从而使树更浅，就像树木（有时也称为树木）的情况一样。另一方面，展开树使树不平衡，将最常访问的项目移动到树的根部附近，同时保持搜索树。了解这些数据结构以及所涉及的权衡将帮助您明智地选择更适合您的应用程序的数据结构。请注意，均衡深度的结构不仅确保最坏的情况是平均情况：它们隐含地假设集合中的所有项目被访问的概率相等——这与帕累托原则完全相反（或者更准确地说，也许，根据齐夫定律）。排序和搜索。数据并不总是以正确的顺序出现，因此在对其应用任何有意义的算法之前，您可能必须对其进行排序。排序是一个复杂的话题，但我认为您真正应该了解的两种算法是 QuickSort 和 Radix Sort。 QuickSort 是一种基于比较的排序，即将元素相互比较以确定它们的相对顺序。最终，QuickSort 进行了足够的比较（对于项目，平均而言，但有一个最坏的情况——这是可以避免的，但现在是另一回事），最终生成一个排序的项目列表。基于比较的排序的理论下限是比较，因此 QuickSort 的平均表现非常好。该算法的极大简单性使其在非常广泛的情况下非常有趣。另一方面，基数排序是一种地址转换排序，它以线性时间对项目进行排序，即 in ，使其比 QuickSort 快得多。它要快得多，但是当键是数字或固定宽度时，基数排序要简单得多；有效地处理可变长度的密钥会使算法稍微复杂一些。在此处和这篇旧的 DDJ 文章中阅读有关 Radix Sort 的更多信息。可以使用基本的时间二分搜索来搜索已排序的数组。创建和搜索高效索引也将在管理和搜索大型数据集方面发挥重要作用。

优先队列。有时您并不真正关心数据集是否完全排序。您只想快速确定其最大（或最小）值项并将其从集合中删除。理想情况下，确定最大项目应该是一个操作，添加和删除值是一个操作。事实证明，堆作为优先队列的实现非常有效。它们不仅具有高效的算法，还可以实现为连续数组，从而避免使用基于指针的数据结构，从而潜在地节省了大量内存。堆有很多应用，范围从调度（确定下一个去的人）到缓存管理（从缓存中删除最旧的项目）。模式匹配和解析。我们每个人都必须编写某种解析器或过滤器。无论是在异常大的日志中查找数据还是读取简单的配置文件。并非总是如此，但通常情况下，最明智的解决方法是使用正则表达式，或者使用库，例如​​ Boost 的 regex 或 Python 的 re，或者自己实现正则表达式算法——这将使它成为疯狂的方式， 我猜。了解它们的工作原理将极大地帮助您处理和过滤结构不充分的数据。不要问为什么 Perl 如此受欢迎。散列。散列函数在密码学、错误检测、缓存管理和高效查找中发挥着核心作用。尽管表面上存在差异——应用程序——所有散列函数都密切相关；事实上，它们在质量上的差异比在性质上的差异更大。散列函数接受一条消息并确定性地生成一个签名，该签名看起来像一个伪随机数，位长，通常相当大，比如 128 或 256。将散列值与原始数据关联起来越困难，就越安全哈希函数是。如果在给定散列值的情况下很难找到原始数据，则该函数可以用作单向函数并用于加密应用程序。如果哈希函数足够好，它可以作为（最有可能的）数据项的唯一标识符，进而可以用于缓存管理或哈希表。在任何一种情况下，您都必须了解碰撞概率（两个或多个项目散列到相同值）的数学原理，以便您可以评估哪种散列方案足以满足您的应用程序。阅读 von Mises 的生日悖论以了解如何计算碰撞概率。不相交集。 Disjoint sets 数据结构是一种辅助结构，您将在各种算法中使用它，无论是图形算法还是图像处理。不相交的集合用于表示单个数组中的多个集合，每个项目都是多个集合之一的成员。这样想来，这听起来是一个比较特殊的情况，但实际上，有许多应用程序，并不都是显而易见的。使用不相交集数据结构最有效地表示图形算法中出现的连接组件。它还可以用于分割图像，这个过程也称为计算连接组件或标记。不相交集的另一个有趣之处在于，操作的效率非常高：使用路径压缩，可以在预期的恒定时间内执行操作！只有两个可能集合的特殊情况会恢复为简单的位图，这是一种易于管理且需要相对较少内存的数据结构 - 使用布隆过滤器可以进一步减少使用，但需要付出一定的代价。图算法和数据结构。诸如计算最小生成树、确定两个节点之间的最短路径、匹配和切割顶点检测等问题会在许多情况下出现。例如，谷歌的 PageRank 就是图算法的一个非常具体的应用。通常，看似无关的问题可以映射到图算法，对于这些算法，已经存在非常有效的算法，可能与动态规划相关。还有大量文献专门讨论用于图的数据结构，考虑了每一种可能的特殊情况：稀疏、密集、集群丰富或小世界网络等。 动态规划。与图算法密切相关，动态规划利用了这样一个事实，即大问题的最佳解决方案可以表示为子问题的最佳组合。并非所有问题都适合这种方法，因为并非每个目标函数都遵循最优性原则，但许多优化问题都符合。动态编程为计算交换内存，这通常是一种有益的权衡。 Memoization 可以被认为是动态编程的一种有限形式，其中对昂贵函数的先前评估被缓存和重用，而不是在再次请求时重新计算。当与优化（或简单的递归）算法结合使用时，记忆化大大降低了计算复杂度。例如，可以使用记忆法及时计算第 n 个斐波那契数，而基本递归公式的结果不少于调用！这里，是菲迪亚斯的数字，黄金比例。状态空间搜索算法。有时，问题的规模或状态空间的广阔性使得无法将问题表示为图形。以国际象棋为例。游戏的不同有效状态的确切数量仍然存在争议，但被认为是 的顺序，以及游戏图中某处周围的弧数，作为计算的香农，因此被称为香农数。在给定任何有效国际象棋位置的情况下，搜索与所有可能游戏相对应的图形以确定最佳移动是不可行的。为了处理这个巨大的状态空间，可以使用许多状态空间搜索算法中的一种，例如有限深度搜索、广度优先搜索，或者如果对目标函数有足够的了解，可以使用 A* 之类的算法。状态空间搜索非常常用于游戏人工智能和其他结构过于复杂、状态空间过大或知之甚少而无法推导出更有效算法的优化问题。

遗传算法与随机优化密切相关，其中在许多不同的点并行搜索状态空间。达尔文主义的比喻在某种程度上是恰当的，因为“基因”（向量）被“变异”（随机变化）以搜索状态空间。只有最适合的（更高价值的向量，在目标函数下）被保留用于下一代“迭代”（迭代）其他“死亡”（被丢弃）。我可以把列表做得更长，至少包括数据压缩等主题，这是个人最喜欢的。我本可以包括一些关于控制理论的内容，这在工业信息学的背景下也非常有用，但我也希望这个列表是一个十诫类型的列表（没有内疚和复仇的上帝的事情），一些会很容易记住，这适用于大多数程序员。当然，您只是阅读了这些内容并在想“为什么不谈论 XYZ”。也许我确实错过了一些重要的事情；也可能是“XYZ”比您想象的更像是一个小众话题。我不能认为这份清单具有任何权威性；然而，它或多或少地遵循典型的“算法导论”一书。无论哪种方式，让见面知道。这篇文章也符合 Gnuvince 评论员之一的“正确工具箱”答案。我再次认为，这并不是要成为我介绍的十个主题中的每一个的大师，而只是精通，并培养反射能力，以查看当前问题与您已经知道的算法之间的相似之处，即使映射可能并不完全不言自明。然而，这不是“从 m 个中挑选 n 个”列表。越多越好。使 n = m。