1.4　算法的效率

回到猜數(shù)字游戲，要猜1到100之間的隨機(jī)整數(shù)，可以采用順序查找算法，即從小到大依次猜，直到猜對為止。最壞的情況下，要猜100次才能猜對。

如果采用二分查找算法，每次猜中間的數(shù)值，依次將查找范圍減半，則對于長度為100的數(shù)組，最壞的情況下，查找范圍依次為100、50、25、12、6、3、1，因此最多7次（log₂100向上取整）就能猜對。

推廣開來，如果數(shù)組大小為n，順序查找最多需要猜n次，二分查找最多需要猜log₂n次。表1-1列出了不同數(shù)據(jù)規(guī)模下，兩種查找算法的效率。數(shù)據(jù)規(guī)模越大，二分查找算法的效率優(yōu)勢越明顯。

表1-1

算法的效率通常使用大O表示法來描述。比如順序查找算法的時間復(fù)雜度記為O(n)，表示對規(guī)模為n的數(shù)據(jù)執(zhí)行順序查找算法的最長運(yùn)行時間為n的常數(shù)倍。二分查找算法的效率可以記為O(log₂n)，表示對規(guī)模為n的數(shù)據(jù)執(zhí)行二分查找算法的最長運(yùn)行時間為n的對數(shù)函數(shù)。

還有一種比二分查找更快的查找算法，那就是哈希查找，也稱為散列查找。哈希查找通過將關(guān)鍵字映射到哈希表中的索引位置來快速定位目標(biāo)數(shù)據(jù)，其時間復(fù)雜度為O(1)。