情景：早上出門，發(fā)現(xiàn)忘帶手機(jī)，最好情況是手機(jī)在門口的臺(tái)子上，最壞情況是找了很久很久才找到，平均情況是找了一會(huì)就找到了。

算法分析：

在一個(gè)有n個(gè)數(shù)字的數(shù)組中查找某個(gè)數(shù)字

最好情況：第一個(gè)數(shù)字就是要查找的，則算法時(shí)間復(fù)雜度O(1)

最壞情況：最后一個(gè)是數(shù)字是要查找的，則算法時(shí)間復(fù)雜度O(n)

平均情況：從概率角度看，要查找的數(shù)字在每個(gè)位置的可能性是相同的，平均查找時(shí)間為n/2,算法時(shí)間復(fù)雜度O(n)

最壞情況：

（1）定義一類輸入，在這類輸入下，算法表現(xiàn)出了最壞的運(yùn)行性能。這類輸入的共同性質(zhì)阻止了算法高效地運(yùn)行，而不只是針對(duì)特定的輸入。

（2）計(jì)算最壞情況的時(shí)間復(fù)雜度

（3）一種保證，保證運(yùn)行時(shí)間不會(huì)更壞了。

（4）是最重要的需求，通常提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間。

（5）對(duì)實(shí)時(shí)性要求非常高的情況，必須分析最壞情況。

比如，汽車防抱死系統(tǒng)，差10毫秒就是人命關(guān)天，時(shí)間就是生命。

這種情況必須把最壞情況的復(fù)雜度控制在某個(gè)閾值之下，平均復(fù)雜度處于次要位置。

平均情況：

（1）平均情況是表示算法在隨機(jī)給定的數(shù)據(jù)上期望的執(zhí)行情況。通俗地說，一些輸入可能會(huì)在某些特殊情況下耗費(fèi)程序大量的時(shí)間，但是大部分的輸入并不會(huì)這樣。這個(gè)衡量標(biāo)準(zhǔn)描述了用戶對(duì)算法性能的期望。

（2）計(jì)算所有情況的平均值

（3）期望的運(yùn)行時(shí)間，是所有情況中最有意義的。

（4）現(xiàn)實(shí)中平均運(yùn)行時(shí)間很難通過分析得到，一般是通過運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來的。

（5）對(duì)實(shí)時(shí)性沒有要求的情況，分析平均情況即可。

比如，在實(shí)驗(yàn)室用某個(gè)算法分析1千萬條數(shù)據(jù)，我們關(guān)心的是總共花多少時(shí)間，所以只需要知道算法的平均時(shí)間復(fù)雜度就夠了。

最好情況：

定義一類輸入，算法在這類輸入下表現(xiàn)出了最好的運(yùn)行性能。對(duì)于這類輸入來說，算法只進(jìn)行很少的計(jì)算。不過在實(shí)際情況下，最好情況很少出現(xiàn)。