2.3.3最好情况

即便最好情况在现实中很少发生，但是了解它还是有必要的。在很多情况下，最好情况能展示算法的最优状况。例如，线性搜索的最好情况是当它在n个元素中搜索v时，第一个元素恰好就是要找的那个。考虑另外一个稍有不同的算法——我们称之为计数搜索（counting search）——它会统计v在列表中出现的次数。如果v的计数是0，那么这个值是不存在的，会返回false；否则返回true。注意，计数搜索总是会搜索整个列表，因此，它在最坏情况下的执行时间是O(n)——和顺序搜索一样——最好情况也是O(n)。也就是说，该算法无法利用最好情况或平均情况下的优势，来让自身获得可能的更好性能。