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