情景：早上出門，發(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í)行情況恩敌。通俗地說(shuō)瞬测，一些輸入可能會(huì)在某些特殊情況下耗費(fèi)程序大量的時(shí)間，但是大部分的輸入并不會(huì)這樣纠炮。這個(gè)衡量標(biāo)準(zhǔn)描述了用戶對(duì)算法性能的期望月趟。
（2）計(jì)算所有情況的平均值
（3）期望的運(yùn)行時(shí)間，是所有情況中最有意義的恢口。
（4）現(xiàn)實(shí)中平均運(yùn)行時(shí)間很難通過(guò)分析得到孝宗，一般是通過(guò)運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來(lái)的。
（5）對(duì)實(shí)時(shí)性沒(méi)有要求的情況耕肩，分析平均情況即可因妇。
比如，在實(shí)驗(yàn)室用某個(gè)算法分析1千萬(wàn)條數(shù)據(jù)猿诸，我們關(guān)心的是總共花多少時(shí)間婚被，所以只需要知道算法的平均時(shí)間復(fù)雜度就夠了。
最好情況：
定義一類輸入梳虽，算法在這類輸入下表現(xiàn)出了最好的運(yùn)行性能址芯。對(duì)于這類輸入來(lái)說(shuō)，算法只進(jìn)行很少的計(jì)算窜觉。不過(guò)在實(shí)際情況下谷炸，最好情況很少出現(xiàn)。
