時(shí)間復(fù)雜度
算法分析
同一問題可用不同算法解決,而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率.算法分析的目的在于選擇合適算法和改進(jìn)算法.一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮.
1裤翩、時(shí)間復(fù)雜度
（1）時(shí)間頻度
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,從理論上是不能算出來的,必須上機(jī)運(yùn)行測(cè)試才能知道.但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試,只需知道哪個(gè)算法花費(fèi)的時(shí)間多,哪個(gè)算法花費(fèi)的時(shí)間少就可以了.并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語句執(zhí)行次數(shù)多,它花費(fèi)時(shí)間就多.一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度.記為T(n).
（2）時(shí)間復(fù)雜度
在剛才提到的時(shí)間頻度中,n稱為問題的規(guī)模,當(dāng)n不斷變化時(shí),時(shí)間頻度T(n)也會(huì)不斷變化.但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律.為此,我們引入時(shí)間復(fù)雜度概念.
一般情況下,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù),用T(n)表示,若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí),T（n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù).記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度,簡稱時(shí)間復(fù)雜度.
在各種不同算法中,若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù),則時(shí)間復(fù)雜度為O(1),另外,在時(shí)間頻度不相同時(shí),時(shí)間復(fù)雜度有可能相同,如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同,但時(shí)間復(fù)雜度相同,都為O(n2).
按數(shù)量級(jí)遞增排列,常見的時(shí)間復(fù)雜度有：
常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n),
線性對(duì)數(shù)階O(nlog2n),平方階O(n2),立方階O(n3),...,
k次方階O(nk),指數(shù)階O(2n).隨著問題規(guī)模n的不斷增大,上述時(shí)間復(fù)雜度不斷增大,算法的執(zhí)行效率越低.
2抗蠢、空間復(fù)雜度
與時(shí)間復(fù)雜度類似,空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量.記作:
S(n)=O(f(n))
我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲(chǔ)單元規(guī)模.
