首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》最好情况

关灯直达底部

知道算法的最好情况是非常有用的,即便这种情况很少发生。在很多情况下,最好情况能让我们看到算法的最优状况。例如,线性搜索的最好情况是当它在n个元素中搜索v的时候,第一个元素恰好就是要找的那个。一个稍微有些不同的算法,我们叫做计数搜索(Counting Search),在n个元素中搜索v,并且记录v在表中出现的次数。如果v的计数是0,那么这个值是不存在的,所以会返回false,否则返回true。注意,计数搜索总是会搜索整个表,因此,它的最坏情况是O(n)(和顺序搜索一样),最好情况还是O(n),所以我们不能够使用这个算法,因为它的最好或者平均情况没有改善性能。