對(duì)于一個(gè)給定的算法，我們要做兩項(xiàng)分析。第一是從數(shù)學(xué)上證明算法的正確性核芽，而在證明算法是正確的基礎(chǔ)上，第二部就是分析算法的時(shí)間復(fù)雜度酵熙。一個(gè)算法的優(yōu)劣往往通過算法復(fù)雜度來衡量轧简，算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度是算法的所需要消耗的時(shí)間匾二，時(shí)間越短哮独，算法越好拳芙。可以對(duì)算法的代碼進(jìn)行估計(jì)皮璧，而得到算法的時(shí)間復(fù)雜度舟扎。一般來說，算法代碼簡(jiǎn)短精悍可以用來減少算法的時(shí)間復(fù)雜度悴务！

空間復(fù)雜度指的是算法程序在執(zhí)行時(shí)所需要的存儲(chǔ)空間睹限。空間復(fù)雜度可以分為以下兩個(gè)方面讯檐！

1.程序的保存所需要的存儲(chǔ)空間資源羡疗。即程序的大小别洪；

2.程序在執(zhí)行過程中所需要消耗的存儲(chǔ)空間資源叨恨，如中間變量等；

一般來說挖垛，程序的大小越小痒钝，執(zhí)行過程中消耗的資源越少，這個(gè)程序就越好痢毒！

算法復(fù)雜度統(tǒng)計(jì)方法

一個(gè)算法是由控制結(jié)構(gòu)（順序送矩、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果闸准。為了便于比較同一個(gè)問題的不同算法益愈，通常的做法是，從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本操作的原操作夷家，以該基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度蒸其。

算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量。而度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法库快。事后統(tǒng)計(jì)的方法和事前分析估算的方法摸袁。事后統(tǒng)計(jì)方法更多的依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素义屏，有時(shí)容易掩蓋算法本身的優(yōu)劣靠汁。因此人們常常采用事前分析估算的方法。在編寫程序前闽铐，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算蝶怔。

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

時(shí)間頻度是一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例兄墅，哪個(gè)算法中語句執(zhí)行次數(shù)多踢星，它花費(fèi)時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度隙咸。記為T(n)沐悦。當(dāng)輸入量n逐漸加大時(shí)成洗，時(shí)間復(fù)雜性的極限情形稱為算法的“漸近時(shí)間復(fù)雜性”。

我們常用大O表示法表示時(shí)間復(fù)雜性藏否，注意它是某一個(gè)算法的時(shí)間復(fù)雜性瓶殃。“O”表示量級(jí) (order)副签，比如說“二分檢索是 O(logn)的”,也就是說它需要“通過logn量級(jí)的步驟去檢索一個(gè)規(guī)模為n的數(shù)組”遥椿。記法 O ( f(n) )表示當(dāng) n增大時(shí)，運(yùn)行時(shí)間至多將以正比于 f(n)的速度增長(zhǎng)继薛。這種漸進(jìn)估計(jì)對(duì)算法的理論分析和大致比較是非常有價(jià)值的修壕，但在實(shí)踐中細(xì)節(jié)也可能造成差異愈捅。例如遏考，一個(gè)O(n²)算法在n較小的情況下可能比 O(nlogn)算法運(yùn)行得更快。當(dāng)然蓝谨，隨著n足夠大以后灌具，具有較慢上升函數(shù)的算法必然工作得更快。

大O表示只是說有上界譬巫，由定義知如果f(n)=O(n)咖楣，那顯然成立f(n)=O(n^2)，它給你一個(gè)上界芦昔，但并不是上確界诱贿，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。如果某個(gè)算法的復(fù)雜性到達(dá)了這個(gè)問題復(fù)雜性的下界咕缎，那就稱這樣的算法是最佳算法珠十。

在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù)凭豪，則時(shí)間復(fù)雜度為O(1)焙蹭。另外，在時(shí)間頻度不相同時(shí)嫂伞，時(shí)間復(fù)雜度有可能相同孔厉，如T(n)=n²+3n+4與T(n)=4n²+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同帖努，都為O(n²)撰豺。

按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1),對(duì)數(shù)階O(log₂n),線性階O(n), 線性對(duì)數(shù)階O(nlog₂n),平方階O(n²)拼余，立方階O(n³),...污桦，k次方階O(n^k),指數(shù)階O(2ⁿ)。隨著問題規(guī)模n的不斷增大姿搜，上述時(shí)間復(fù)雜度不斷增大寡润，算法的執(zhí)行效率越低捆憎。

常見的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜O(log₂n)＜Ο(n)＜O(nlog₂n)＜O(n²)＜O(n³)＜…＜O(2ⁿ)＜Ο(n!)

時(shí)間復(fù)雜度的計(jì)算

（1）找出算法中的基本語句；算法中執(zhí)行次數(shù)最多的那條語句就是基本語句梭纹，通常是最內(nèi)層循環(huán)的循環(huán)體躲惰。

（2） 計(jì)算基本語句的執(zhí)行次數(shù)的數(shù)量級(jí)；只需計(jì)算基本語句執(zhí)行次數(shù)的數(shù)量級(jí)变抽，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可础拨，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析绍载，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率诡宗。

（3）用大Ο記號(hào)表示算法的時(shí)間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中击儡。如果算法中包含嵌套的循環(huán)塔沃，則基本語句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)阳谍，則將并列循環(huán)的時(shí)間復(fù)雜度相加蛀柴。

（4）對(duì)于一些簡(jiǎn)單的輸入輸出語句或賦值語句,近似認(rèn)為需要O(1)時(shí)間。對(duì)于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時(shí)間可采用大O下"求和法則"矫夯。對(duì)于選擇結(jié)構(gòu),如if語句,它的主要時(shí)間耗費(fèi)是在執(zhí)行then字句或else字句所用的時(shí)間,需注意的是檢驗(yàn)條件也需要O(1)時(shí)間鸽疾。對(duì)于循環(huán)結(jié)構(gòu),循環(huán)語句的運(yùn)行時(shí)間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗(yàn)循環(huán)條件的時(shí)間耗費(fèi),一般可用大O下"乘法法則"。乘法法則: 是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1T2=O(f(n)g(n))训貌。

對(duì)于復(fù)雜的算法,可以將它分成幾個(gè)容易估算的部分,然后利用求和法則和乘法法則技術(shù)整個(gè)算法的時(shí)間復(fù)雜度制肮。另外還有以下2個(gè)運(yùn)算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個(gè)正常數(shù)递沪。

for (i=1; i<=n; i++)  
   x++;  
for (i=1; i<=n; i++)  
　for (j=1; j<=n; j++)  
      x++; 

第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n)豺鼻，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n²)，則整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n²)=Ο(n²)区拳。

常見的時(shí)間復(fù)雜度說明

1拘领、O(1)

    Temp=i; i=j; j=temp;                    

以上三條單個(gè)語句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)樱调。算法的時(shí)間復(fù)雜度為常數(shù)階约素，記作T(n)=O(1)。注意：如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長(zhǎng)笆凌，即使算法中有上千條語句圣猎，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)乞而。

2送悔、O(n²)

sum=0；                       (1)
for(i=1;i<=n;i++)            (n+1)
  for(j=1;j<=n;j++)          (n^2)
    sum++；                  (n^2)

解：因?yàn)棣?2n²+n+1)=n²（Θ即：去低階項(xiàng)欠啤，去掉常數(shù)項(xiàng)荚藻，去掉高階項(xiàng)的常參得到），所以T(n)=O(n²)洁段；

for (i=1;i<n;i++)  
 {   
   y=y+1;         ①     
   for (j=0;j<=(2*n);j++)      
      x++;         ②        
 }  

解： 語句1的頻度是n-1应狱，語句2的頻度是(n-1)*(2n+1)=2n²-n-1。f(n)=2n²-n-1+(n-1)=2n²-2祠丝；又Θ(2n²-2)=n²疾呻，該程序的時(shí)間復(fù)雜度T(n)=O(n²)。

一般情況下写半，對(duì)步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)岸蜗，忽略該語句中步長(zhǎng)加1、終值判別叠蝇、控制轉(zhuǎn)移等成分璃岳，當(dāng)有若干個(gè)循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的蟆肆。

3矾睦、O(n)

a=0;  
b=1;                      ①  
for (i=1;i<=n;i++)        ②  
{    
 s=a+b;　　　　③  
 b=a;　　　　⊙坠Α④    
 a=s;　　　　　⑤  
} 

解： 語句1的頻度：2,
語句2的頻度： n,
語句3的頻度： n-1,
語句4的頻度：n-1,
語句5的頻度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

4缓溅、O(log2n)

i=1;       ①  
while (i<=n)  
  i=i*2;   ② 

解： 語句1的頻度是1,
設(shè)語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log₂n
取最大值f(n)=log₂n,
T(n)=O(log₂n )

5蛇损、O(n³)

for(i=0;i<n;i++)  
 {    
    for(j=0;j<i;j++)    
    {  
     for(k=0;k<j;k++)  
        x=x+2;    
    }  
 }

解：3層循環(huán)，由上可知復(fù)雜度為O(n³).

常用的算法的時(shí)間復(fù)雜度和空間復(fù)雜度

同一個(gè)算法處理不同的輸入數(shù)據(jù)所消耗的資源也可能不同坛怪，所以分析一個(gè)算法的復(fù)雜度時(shí)淤齐，主要有三種情況可以考慮，最差情況(Worst Case)下的袜匿，平均情況(Average Case)的更啄， 最好情況(Best Case)下的。我們查找一個(gè)有n個(gè)隨機(jī)數(shù)字?jǐn)?shù)組中的某個(gè)數(shù)字居灯，最好的情況是第一個(gè)數(shù)字就是祭务，那么算法的時(shí)間復(fù)雜度為O(1)，但也有可能這個(gè)數(shù)字就在最后一個(gè)位置上待著怪嫌，那么算法的時(shí)間復(fù)雜度就是O(n)义锥，這是最壞的一種情況了。最壞情況運(yùn)行時(shí)間是一種保證岩灭，那就是運(yùn)行時(shí)間將不會(huì)再壞了拌倍。在應(yīng)用中，這是一種最重要的需求，通常柱恤，除非特別指定数初，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間。

平均運(yùn)行時(shí)間也就是從概率的角度看梗顺，這個(gè)數(shù)字在每一個(gè)位置的可能性是相同的妙真，所以平均的查找時(shí)間為n/2次后發(fā)現(xiàn)這個(gè)目標(biāo)元素。平均情況更能反映大多數(shù)情況下算法的表現(xiàn)荚守。平均情況分析就是對(duì)所有輸入尺寸為n的輸入珍德，讓算法運(yùn)轉(zhuǎn)一遍，然后取它們的平均值矗漾。當(dāng)然锈候，實(shí)際中不可能將所有可能的輸入都運(yùn)行一遍，因此平均情況通常指的是一種數(shù)學(xué)期望值敞贡，而計(jì)算數(shù)學(xué)期望值則需要對(duì)輸入的分布情況進(jìn)行假設(shè)泵琳，一般都是通過運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來的。

考慮最好情況的復(fù)雜度更是沒有意義誊役。幾乎所有的算法你都可以稍微修改一下获列，以獲得很好的最好情況下的復(fù)雜度(要看輸入數(shù)據(jù)的結(jié)構(gòu)，可以是O(1)蛔垢。怎樣修改呢? 預(yù)先計(jì)算好某一輸入的答案击孩，在算法的開始部分判斷輸入，如果符合鹏漆，給出答案巩梢。