算法的效率

算法的效率主要由以下兩個(gè)復(fù)雜度來(lái)評(píng)估：

• 時(shí)間復(fù)雜度：評(píng)估執(zhí)行程序所需的時(shí)間酬屉。可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?/p>

• 空間復(fù)雜度：評(píng)估執(zhí)行程序所需的存儲(chǔ)空間蹭沛∨沤兀可以估算出程序?qū)τ?jì)算機(jī)內(nèi)存的使用程度娱节。

設(shè)計(jì)算法時(shí)挠蛉，一般是要先考慮系統(tǒng)環(huán)境，然后權(quán)衡時(shí)間復(fù)雜度和空間復(fù)雜度肄满，選取一個(gè)平衡點(diǎn)谴古。不過(guò)，時(shí)間復(fù)雜度要比空間復(fù)雜度更容易產(chǎn)生問(wèn)題稠歉，因此算法研究的主要也是時(shí)間復(fù)雜度掰担，不特別說(shuō)明的情況下，復(fù)雜度就是指時(shí)間復(fù)雜度怒炸。

時(shí)間復(fù)雜度

時(shí)間頻度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間带饱，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道阅羹。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試勺疼，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了捏鱼。

一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例执庐，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多导梆。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度轨淌。記為T(mén)(n)。

時(shí)間復(fù)雜度

前面提到的時(shí)間頻度T(n)中看尼，n稱為問(wèn)題的規(guī)模递鹉，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化藏斩。

但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律躏结，為此我們引入時(shí)間復(fù)雜度的概念。一般情況下灾茁，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)窜觉，用T(n)表示谷炸，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無(wú)窮大時(shí)禀挫，T（n)/f(n)的極限值為不等于零的常數(shù)旬陡，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)，記作

T(n) = O(f(n))

它稱為算法的漸進(jìn)時(shí)間復(fù)雜度语婴，簡(jiǎn)稱時(shí)間復(fù)雜度描孟。

大O表示法

像前面用O( )來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法，我們稱之為大O表示法砰左。

算法復(fù)雜度可以從最理想情況匿醒、平均情況和最壞情況三個(gè)角度來(lái)評(píng)估，由于平均情況大多和最壞情況持平缠导，而且評(píng)估最壞情況也可以避免后顧之憂廉羔，因此一般情況下，我們?cè)O(shè)計(jì)算法時(shí)都要直接估算最壞情況的復(fù)雜度僻造。

大O表示法O(f(n)中的f(n)的值可以為1憋他、n、logn髓削、n2等竹挡，因此我們可以將O(1)、O(n)立膛、O(logn)揪罕、O(n2)分別可以稱為常數(shù)階、線性階宝泵、對(duì)數(shù)階和平方階好啰，那么如何推導(dǎo)出f(n)的值呢？我們接著來(lái)看推導(dǎo)大O階的方法鲁猩。

推導(dǎo)大O階

推導(dǎo)大O階坎怪，我們可以按照如下的規(guī)則來(lái)進(jìn)行推導(dǎo)，得到的結(jié)果就是大O表示法：

• 1.用常數(shù)1來(lái)取代運(yùn)行時(shí)間中所有加法常數(shù)廓握。
• 2.修改后的運(yùn)行次數(shù)函數(shù)中搅窿，只保留最高階項(xiàng)
• 3.如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)隙券。

1. 常數(shù)階 O(1)

int sum = 0,n = 100; //執(zhí)行一次  
sum = (1+n)*n/2; //執(zhí)行一次  
System.out.println (sum); //執(zhí)行一次 

上面算法的運(yùn)行的次數(shù)的函數(shù)為f(n)=3男应，根據(jù)推導(dǎo)大O階的規(guī)則1，我們需要將常數(shù)3改為1娱仔，則這個(gè)算法的時(shí)間復(fù)雜度為O(1)沐飘。如果sum = （1+n）*n/2這條語(yǔ)句再執(zhí)行10遍，因?yàn)檫@與問(wèn)題大小n的值并沒(méi)有關(guān)系，所以這個(gè)算法的時(shí)間復(fù)雜度仍舊是O(1)耐朴，我們可以稱之為常數(shù)階借卧。

只要算法中不存在循環(huán)語(yǔ)句、遞歸語(yǔ)句筛峭，即使有成千上萬(wàn)行的代碼铐刘，其時(shí)間復(fù)雜度也是O(1)。

2. 線性階 O(n)

線性階主要要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況影晓，如下所示镰吵。

for(int i=0;i<n;i++){
//時(shí)間復(fù)雜度為O(1)的算法
...
}

上面算法循環(huán)體中的代碼執(zhí)行了n次，因此時(shí)間復(fù)雜度為O(n)挂签。

3. 對(duì)數(shù)階 O(logn)

int number=1;
while(number<n){
number=number*2;
//時(shí)間復(fù)雜度為O(1)的算法
...
}

可以看出疤祭，隨著number每次乘以2后，都會(huì)越來(lái)越接近n饵婆，當(dāng)number不小于n時(shí)就會(huì)退出循環(huán)勺馆。假設(shè)循環(huán)的次數(shù)為X，則由2^x=n得出x=log?n啦辐，因此得出這個(gè)算法的時(shí)間復(fù)雜度為O(logn)谓传。

3. 平方階 O(n2)

for(int i=0;i<n;i++){   
    for(int j=0;j<n;i++){
        //復(fù)雜度為O(1)的算法
        ... 
    }
}

內(nèi)層循環(huán)的時(shí)間復(fù)雜度在講到線性階時(shí)就已經(jīng)得知是O(n)蜈项，現(xiàn)在經(jīng)過(guò)外層循環(huán)n次芹关，那么這段算法的時(shí)間復(fù)雜度則為O(n2)。
接下來(lái)我們來(lái)算一下下面算法的時(shí)間復(fù)雜度：

for(int i=0;i<n;i++){   
    for(int j=i;j<n;i++){
        //復(fù)雜度為O(1)的算法
        ... 
    }
}

當(dāng)i=0時(shí)紧卒，內(nèi)循環(huán)執(zhí)行了n次侥衬；i=1時(shí)內(nèi)循環(huán)執(zhí)行了n-1次，當(dāng)i=n-1時(shí)執(zhí)行了1次跑芳，我們可以推算出總的執(zhí)行次數(shù)為：

n+(n-1)+(n-2)+(n-3)+……+1 
=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+…… +[n-(n-1)+n] - (1+2+...+n)
=n(n+1)-n(1+n)/2
=n(n+1)/2 
=n2/2+n/2

根據(jù)此前講過(guò)的推導(dǎo)大O階的規(guī)則的第二條：只保留最高階轴总，因此保留n2/2。根據(jù)第三條去掉和這個(gè)項(xiàng)的常數(shù)博个，則去掉1/2,最終這段代碼的時(shí)間復(fù)雜度為O(n2)怀樟。

4. 其他常見(jiàn)復(fù)雜度

除了常數(shù)階、線性階盆佣、平方階往堡、對(duì)數(shù)階，還有如下時(shí)間復(fù)雜度：

• O(nlogn)共耍，可以稱為nlogn階

如果一段代碼的時(shí)間復(fù)雜度是 O(logn)虑灰，循環(huán)執(zhí)行 n 遍，時(shí)間復(fù)雜度就是 O(nlogn)痹兜，歸并排序穆咐、快速排序的時(shí)間復(fù)雜度都是 O(nlogn)。

• O(√n)，可以稱為平方根階
• O(n3)对湃，可以稱為立方階
• O(2?)崖叫，可以稱為指數(shù)階
• O(n!)，可以稱為階乘階

復(fù)雜度的比較

從上表可以看出拍柒，O(n)归露、O(logn)、O(√n )斤儿、O(nlogn )隨著n的增加剧包，復(fù)雜度提升不大，因此這些復(fù)雜度屬于效率高的算法往果，反觀O(2?)和O(n!)當(dāng)n增加到50時(shí)疆液，復(fù)雜度就突破十位數(shù)了，這種效率極差的復(fù)雜度最好不要出現(xiàn)在程序中陕贮，因此在動(dòng)手編程時(shí)要評(píng)估所寫(xiě)算法的最壞情況的復(fù)雜度堕油。

常用的時(shí)間復(fù)雜度按照耗費(fèi)的時(shí)間從小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2?) < O(n!)

最好、最壞肮之、平均掉缺、均攤時(shí)間復(fù)雜度

• 最壞情況時(shí)間復(fù)雜度：代碼在最理想情況下執(zhí)行的時(shí)間復(fù)雜度。
• 最好情況時(shí)間復(fù)雜度：代碼在最壞情況下執(zhí)行的時(shí)間復(fù)雜度戈擒。
• 平均時(shí)間復(fù)雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示眶明。
• 均攤時(shí)間復(fù)雜度：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級(jí)別的復(fù)雜度，個(gè)別情況是高級(jí)別復(fù)雜度且發(fā)生具有時(shí)序關(guān)系時(shí)筐高，可以將個(gè)別高級(jí)別復(fù)雜度均攤到低級(jí)別復(fù)雜度上搜囱。這種復(fù)雜度分析法我們就叫做均攤復(fù)雜度分析法。最典型的例子就是我們寫(xiě)一個(gè)動(dòng)態(tài)數(shù)組這樣的一個(gè)類(lèi)柑土，動(dòng)態(tài)數(shù)組每添加一個(gè)元素蜀肘，或者刪除一個(gè)元素，我們就要用到均攤復(fù)雜度分析法稽屏。

同一段代碼在不同情況下出現(xiàn)量級(jí)差別時(shí)才需要區(qū)別這四種復(fù)雜度扮宠。大多數(shù)情況下，是不需要區(qū)別分析它們的狐榔。