算法(Algorithms)的復雜度(Complexity)是指運行一個算法所需消耗的資源(時間或者空間)。同一個算法處理不同的輸入數據所消耗的資源也可能不同，所以分析一個算法的復雜度時，主要有三種情況可以考慮，最差情況(Worst Case)下的，平均情況(Average Case)的， 最好情況(Best Case)下的。不管是在實際應用中，還是計算機理論的研究中，大多都只考慮最差情況下的復雜度分析。為什么呢？這里給出四點原因,
- 最差情況下的復雜度是所有可能的輸入數據所消耗的最大資源，如果最差情況下的復雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。
- 某些算法經常遇到最差情況。比如一個查找算法，經常需要查找一個不存在的值。
- 也許你覺得平均情況下的復雜度更吸引你，可是平均情況也有幾點問題。第一，難計算，多數算法的最差情況下的復雜度要比平均情況下的容易計算的多，第二，有很多算法的平均情況和最差情況的復雜度是一樣的. 第三，什么才是真正的平均情況？如果你假設所有可能的輸入數據出現的概率是一樣的話，也是不合理的。其實多數情況是不一樣的。而且輸入數據的分布函數很可能是你沒法知道。
- 考慮最好情況的復雜度更是沒有意義。幾乎所有的算法你都可以稍微修改一下，以獲得很好的最好情況下的復雜度(要看輸入數據的結構，可以是O(1))。怎樣修改呢? 預先計算好某一輸入的答案，在算法的開始部分判斷輸入，如果符合，給出答案。
轉載請保留
http://www.tkk7.com/xilaile/archive/2007/03/30/107374.html