第1章 绪论
1.1 评估算法
除了最直观的应用之外，算法是所有程序的核心和灵魂。算法一般被设计用于以最小的代价高效地解决特定的问题。算法的价值一般取决于两方面因素：如何恰当地解决问题以及如何高效地实现解决方案。这些是算法分析的定性和定量方面。
对于许多算法，质量不是一个问题。例如，对于排序算法，必须保证每次都对所有元素正确地进行了排序。一旦出错，就必须丢弃它并且严格说来不能将其视为一种算法。在其他领域，不能基于这种简单的通过／失败测试来度量质量。例如，在第4章中介绍的Soundex算法允许检索听起来相同的单词或名字。与排序算法不同，可以调整Soundex算法，以寻找接近的匹配或者相当宽泛的匹配；这取决于实现算法的方式和开发人员的需求。在这种情况下，质量是可度量的并且是算法的重要方面，并且指导我们认真选择不同的解决方案。
算法设计的定量方面尝试确定算法所需的资源。一般来说，最重要的度量标准是时间：即算法运行得有多快？偶尔，计算机资源（比如可用的内存）也是一个重要因素。度量性能
与基准的性能不同，算法的性能很少依据时间来加以说明。在论及排序例程时，你几乎从未听到它完成排序要花费8．62秒这样的说明。这有一个很好的理由：这种计时难以复制，并且通常依赖于正在处理的数据的具体特征。算法不依赖于计时，而是依赖于一个直观的方程，以显示输入的大小与性能之间的关系。用于显示这种关系的传统方法是使用符号D，称为大O表示法（big.oh notation）。其工作方式是：假定你有一个算法，它简单地通读一个文本文件，从中查找单词flea。一种合理的方法是寻找字母f的每个实例（参见第4章）。当找到一个f，该算法就测试4个字母的序列，看看它是不是单词flea。在这个示例中，显然执行时间直接与文本文件的大小成正比。如果给定的文件包含Ⅳ个字符，那么我们就说该算法的执行时间的界限是O（N）。你会注意到这种表述没有考虑到可能影响性能的其他因素——例如，字母f在文本中出现的频繁程度。在查找字符串时（比如fleas rarely wear collars），字符串的长度以及其中相似字符串（比如fleasrarely weal“colors）出现的频率也会影响性能。不过，严格来讲，这些因素是要处理的数据的函数，而不是算法的函数。因此，在大O表示法中，它们不会出现在公式中。该表示法只是简单地说明数据规模（一般用Ⅳ表示，偶尔也用n表示）与算法的典型性能之间的关系。
……
