1.8　随机算法

Quicksort平均情况性能的分析取决于随机顺序的输入。在许多实际情况下，这个假设可能不是严格有效的。一般来说，这种情况反映了算法分析中最严峻的挑战之一：需要适当地将可能在实际中出现的输入模型公式化。

幸运的是，常常存在能够规避这种缺陷的方法：在使用算法之前，先将输入“随机化”。对于排序算法而言，这相当于在排序之前将输入的序列随机排序。（相关算法的具体实现，请见第7章。）如果做到了这一点，那么前面提到的关于性能的概率论述就是完全有效的，并且无论实际中输入序列的顺序如何，都能准确地预测性能。

通过随机选择（与任意的特定选择相反），只要算法可以采用几种方案之一，就常常能够以较少的工作实现相同的结果。对于Quicksort，这个原理相当于随机选取元素作为分隔元，而不是每次都使用数组末尾的元素。如果这种方法能严谨地实现（保留子序列的随机性），则验证了先前的概率分析是有效的。（对于小型子序列应该使用截止的做法，因为它使生成随机数的数目大约减少 M。）随机算法的许多其他例子可以在参考资料[23]和[25]中找到。这种算法在实践中极具价值，因为它们利用随机性获得效率提升，并以高概率避免出现最劣情况的性能。此外，我们还可以对性能做准确的概率表述，进一步激励人们研究先进技术来获得这样的结果。

我们一直在考虑的关于Quicksort分析的例子可能说明了一种理想方法，但并不是所有的算法都能像这种方法一样被顺利地处理。像这样全面地进行分析需要花费相当多的精力，而这种精力应该留给最重要的算法。幸运的是，我们将看到存在许多基本方法，确实具备使分析值得深入进行的基本要素。

● 可以指定现实的输入模型。

● 可以推导出描述成本的数学模型。

● 可以得到简捷、准确的结果。

● 可以用结果来比较变体，可以与其他算法进行比较，而且有助于调整算法的参数值。

在本书中，我们考虑了许多这类方法，并重点研究使第2点和第3点成立的数学方法。

大多数情况下，我们跳过上述方法中程序特定（依赖于实现）的部分，是为了专注于算法设计，此时运行时间的粗略估计可能已经足够了；或者是为了专注于数学分析，此时数学问题所涉及的公式与求解方法是我们最感兴趣的问题。这些是涉及最重要的智力性挑战的领域，我们应该给予足够关注。

上文已经提到，目前在计算机的一般使用中，算法分析面临一个重要挑战，即如何把实际代表输入的模型以及易于进行分析问题的模型公式化。对此我们不必介意，因为存在一大类组合学（combinatorial）算法，对这类算法而言模型是自然的。在本书中，我们从一些细节入手考虑了这类算法的例子以及它们操作的基本结构。我们研究排列、树、字符串、字典树、单词和映射，是因为它们既是广泛研究的组合学结构，也是广泛使用的数据结构，还因为“随机”结构同时具备直接和现实的特点。

从第2章到第5章，我们着重讨论适用于算法性能研究的数学分析技术。除了算法分析，这些技术在许多其他应用中也非常重要。为了给本书后面的应用做准备，我们讨论的范围将进一步展开。然后，在第6章到第9章，我们将这些技术应用于分析某些基本的组合学算法，其中包含若干具有实际意义的问题。在各种各样的计算机应用中，这类算法中的许多算法都具有基础性的重要作用，因此需要对其进行详细分析。在某些情况下，有些看似很简单的算法却可能导致非常复杂的数学分析；而在另一些情况下，有些看上去相当复杂的算法却可能被直接简单地进行处理。在以上两种情况中，分析都能揭示在实际使用中具有直接影响的算法之间的重要区别。

重要的是，尽管现代计算机代数系统（例如Maple、Mathematica和Sage）在检查和开发结果方面是不可或缺的，但我们依旧要讲授并展现经典风格的数学推导。我们在这里提供的材料可以被视为学习如何有效利用这种系统的准备。

我们的重点是研究确定算法实现性能特征的有效方法。因此，我们所提供的程序都是以广泛使用的编程语言（Java）来编写的。这种方法具有一个优点，即程序是对算法完整而明确的描述。这种方法还有另一个优点，即读者可以通过运行经验测试来验证数学结果。我们的程序一般来源于Sedgewick和Wayne的Algorithms，4th edition[30]一书中的完整Java实现程序。我们尽可能地使用标准语言机制，以便熟悉其他编程环境的人能将其翻译为合适的编程语言。有关大多数程序的更多信息可以在参考资料[30]中找到。

当然，与介绍性材料中所讨论的内容相比，我们涉及的基本方法适用于更广泛的算法和结构。自20世纪中期计算机出现以来，研究者开发了大量组合算法，而我们仅讨论其中的几种。我们不涉及从图像处理到生物信息学等诸多应用领域，在这些领域中已经证明算法是有效的，并且已深入研究了某些算法。我们仅提及简单的方法，如平摊分析和概率性方法，这些方法已经成功应用于一些重要算法的分析。不过，为了鉴赏算法分析研究资料中的材料，我们希望读者通过掌握这本书的介绍性材料来做充足的准备。除了先前引用的Knuth、Sedgewick和Wayne以及Cormen、Leiserson、Rivest和Stein的图书，关于算法分析和算法理论的其他信息来源是参考资料[11]、参考资料[7]，以及参考资料[16]。

同样重要的是，我们讨论组合性的分析问题，它使我们能够开发一般的方法，这些方法可能有助于分析那些未来的、尚未被发现的算法。我们使用的方法源于组合学和渐近分析的经典领域，可以用这些领域中的经典方法来统一处理各种各样的问题。在我们的另一部书——Analytic Combinatorics[10]（《分析组合学》）中，对这一过程有详细的论述。最后，我们不仅能依据简单的形式描述直接将组合计数问题公式化，还可以直接根据这些公式推导出结果的渐近估计。

本书涵盖了重要的基本概念，而与此同时，参考资料[10]以及其他研究先进方法的书籍又为更先进的算法奠定了基础，例如Szpankowski有关字（有时也称为“单词”）的算法研究[32]，或者Drmota对树的研究[8]。参考资料[12]是涉及更多所用数学资料的良好来源；参考资料[5]（组合学）和参考资料[14]（用于分析）中也有相关内容。一般来说，我们在本书中运用初等组合学和实际分析，而参考资料[10]则从组合学角度来研究更先进的方法，它依赖于对渐近性的复杂分析。

经典数学函数的性质是本书内容的重要组成部分。由Abramowitz和Stegun撰写的Handbook of Mathematical Functions[1]（《数学函数手册》）内容经典，是数学家几十年来不可或缺的参考依据，当然也是本书创作的滥觞。最近出版了一个旨在取代它的新参考资料，并附有相关的在线资料[24]。实际上，在网络上，如维基百科（Wikipedia）和数学世界（Mathworld[35]）等资源中，能够越来越多地找到这种参考资料。另一个重要资源是Sloane的整数序列线上百科全书（On-Line Encyclopedia of Integer Sequences[31]）。

我们的出发点是研究那些广泛使用的基本算法的特点，但本书的主要目的是为我们遇到的组合学和分析方法提供连贯的处理。在适当的时候，我们详细研究那些自然产生但可能不适用于任何（当前已知）算法的数学问题。在使用这种方法的过程中，我们显然涉及范围和多样性的问题。此外，从全书的例子中可以看出，我们求解的问题与许多重要的应用直接相关。