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