基础#

简介#

当你设计和分析算法时，你需要能够描述它们的运行方式和设计方法。你还需要一些数学工具来证明你的算法是正确且高效的 。本部分将为你打下基础，后续章节将基于此基础进一步展开。

第1章概述了算法及其在现代计算系统中的地位。本章定义了什么是算法，并列举了一些示例。同时，本章还论证了将算法视为一种技术的重要性，与快速硬件、图形用户界面、面向对象系统和网络等技术并列。

在第2章中，我们介绍了第一个算法，它们解决了对n个数字序列进行排序 的问题。虽然这些算法是用伪代码编写的，不能直接转换为任何常规编程语言，但它们清晰地传达了算法的结构，使你能够用自己选择的语言来实现它们。我们研究的排序算法包括插入排序，它采用增量方法，以及归并排序，它使用一种称为“分而治之”的递归技术。虽然每种算法所需的时间都会随着n值的增加而增加，但两种算法的增长速度不同。我们在第二章中确定了这些运行时间，并开发了一种有用的“渐近”符号来表示它们。

第3章 精确定义了渐近符号。我们将使用渐近符号来从上界和下界限制函数的增长，通常是描述算法运行时间的函数。本章首先非正式地定义了最常用的渐近符号，并举例说明如何应用它们。接着正式定义了五种渐近符号，并介绍了如何组合使用它们的惯例。第3章的其余部分主要是数学符号的介绍，更多是为了确保你使用的符号与本书中的一致，而不是教你新的数学概念。

第4章 进一步探讨了第2章介绍的分治法。它提供了两个额外的分治算法示例，用于乘方矩阵，包括斯特拉森的惊人方法。第4章包含了解决递归的方法，这些方法对于描述递归算法的运行时间非常有用。在替代方法中，你猜测一个答案并证明其正确性。递归树提供了一种生成猜测的方法。第4章还介绍了强大的“主方法”技术，你可以经常使用它来解决分治算法中出现的递归问题。尽管本章提供了一个基础定理的证明，该定理是主定理的基础，但你可以在不深入研究证明的情况下使用主方法。第4章以一些高级主题作为结尾。

第五章 介绍了概率分析和随机算法。通常情况下，你会使用概率分析来确定算法的运行时间，尤其是在由于存在固有的概率分布，导致相同大小的不同输入可能会有不同运行时间的情况下。有时，你可能会假设输入符合已知的概率分布，从而对所有可能的输入进行平均运行时间的计算。而在其他情况下，概率分布并非来自输入，而是来自算法执行过程中所做的随机选择。一个算法的行为不仅由其输入决定，还由随机数生成器产生的值决定，这样的算法就是随机算法。你可以使用随机算法来对输入施加概率分布，从而确保没有特定输入总是导致性能不佳，或者甚至可以限制允许在一定范围内产生错误结果的算法的错误率。

附录A-D 包含了其他数学材料，在阅读本书时你会发现这些内容很有帮助。你可能在阅读本书之前已经见过附录章节中的大部分内容（尽管我们使用的具体定义和符号惯例在某些情况下可能与你以前见过的有所不同），因此你应该将附录视为参考资料。另一方面，你可能还没有见过第一部分的大多数内容。第一部分的所有章节和附录都带有教程的风格。

评论