算法分析

无论是在设计还是在应用一种广泛认可的算法时，我们必须了解这种算法的性能如何。算法的性能可以通过很多方面评判，但是通常我们最关心的算法是运算速度。但有些时候，如果一种算法消耗了大量的存储空间，那么我们也要关注算法对内存空间的要求。不管如何，都要一种标准和确定的方法来确定算法的性能。

之所以要了解算法的性能，去原因是很多方面的。例如：当要解决一个问题时，有很多算法可供选择，理解算法的性能有助于区分它们，如果了解每种算法的性能就能够有效地帮助我们解决问题。举例来说，垃圾回收算法，它用来回收堆上分配的动态存储空间(见第3章)，并且需要相当长的时间来运行。认识到这点之后，我们就能非常注意只在适当的时候运用此算法，就像LISP和Java所做的那样。

本章内容包括：

最坏情况分析

这是大多数算法都采用的评估方法。在其他情况下，我们可能会考虑算法的平均情况和最佳情况。但是，对最坏情况的分析同样会带来一些好处。

O表示法

这是表示算法性能的最为常用的正式方法。在一定的条件因素下，O表示法指明一个函数的上限。

计算的复杂度

资源消耗的大小往往与算法所需要处理的数据量地方哦大小相辅相成。O表示法可以很好表示一个算法的复杂度。

最坏情况分析

在所有的情况下，绝大多数算法都会表现出不同的性能；并且，随着传人数据的不同，算法的表现也不相同。通常用来判断性能的三种情况是：最佳情况、平均情况与最坏情况。对于任何算法来说，理解每种情况是如何生产的对于分析算法来说非常重要，因为算法在不同的情况下性能差异可能很大。看一种线性收索的简单算法。线性搜索是一种自然的但效率低下的搜索技术，它简单地从数据集的头部顺序遍历到尾部。在最佳情况下，要查找的元素处于数据集的第一个位置，所以在仅仅遍历一个元素之后就找到想查找的元素，然而，在最坏情况下，要查找的元素处于数据集的最后一个位置，所以必须在遍历完所有的元素之后才能找到要查找的元素。在平均情况下，可能在数据集的中间某一个位置找到元素。