查找算法性能评价-《数据结构与算法：Java版》

一般分析查找算法的性能指标包括算法的最佳情况、算法的最差情况和算法的平均情况，以顺序表的查找为例，分析顺序查找的性能。

（1） 算法的最佳情况。如果表中的第一个记录恰恰就是要找的记录，于是只要比较一个记录就行了，这是算法运行时间的最佳情况。

（2） 算法的最差情况。如果表中最后一个记录才是要找的记录，则要比较所有的记录，这是算法运行时间的最差情况。

（3） 算法的平均情况。如果对应的记录是在表中的其他位置，按出现位置等概情况下计算平均比较次数，就会发现算法平均查找的记录是总记录个数的一半，这是算法运行时间的平均情况。

一般来说，算法的最佳情况，没有实际意义，因为它发生的概率很小，而且对条件的要求也很苛刻。而算法的最差情况可以知道算法的最差运行时间是否在算法设计的要求之内，这一点在实际应用中十分重要。通常情况下更希望知道算法运行的平均情况，它是算法运行的“典型”表现。

对于算法运行的平均情况，一般会分析平均情况下查找成功时的算法执行时间及查找不成功时算法执行时间。而“执行时间”一般用“平均查找长度”来评价。(www.xing528.com)

查找算法性能评价指标——平均查找长度（Average Search Length，ASL），即

式中，ip为表中第i个记录的查找概率；ic为要找到第i个记录的比较次数。

ASL有查找成功的平均查找长度ASL成功和查找不成功的平均查找长度ASL不成功。

下面介绍的几种查找算法，给出算法的时间分析和分析结果。值得注意的是，在介绍查找算法时，均只介绍关键字的查找，实际中查找关键字成功后会根据关键字找到关联的数据记录的其他内容（Others）。