漸進(jìn)時(shí)間復(fù)雜度的計(jì)算(編輯修改稿)
2025-08-21 22:13 本頁面
【文章內(nèi)容簡介】 解答：T(n)=n1， T(n)=O(n)， 這個(gè)函數(shù)是按線性階遞增的。(2) x=n。 // n1while (x=(y+1)*(y+1))y++。解答：T(n)=n1/2 ，T(n)=O(n1/2)，最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個(gè)按平方根階遞增的函數(shù)。(3) x=91。 y=100。while(y0)if(x100){x=x10。y。}else x++。解答： T(n)=O(1)，這個(gè)程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到n沒有? 沒。這段程序的運(yùn)行是和n無關(guān)的，就算它再循環(huán)一萬年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。 時(shí)間復(fù)雜度（1）時(shí)間頻度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測試才能知道。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試，只需知道哪個(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)也會不斷變化。但有時(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ù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(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ù)量級遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n),線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...，k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。空間復(fù)雜度 與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲空間的度量。記作:S(n)=O(f(n))我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。討論方法與時(shí)間復(fù)雜度類
化學(xué)相關(guān)推薦
鄂ICP備17016276號-1