本文部分摘抄于此
算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度寓免。
時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量；
而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。
（算法的復(fù)雜性體現(xiàn)在運行該算法時的計算機(jī)所需資源的多少上转质，計算機(jī)資源最重要的是時間和空間（即寄存器）資源，因此復(fù)雜度分為時間和空間復(fù)雜度）炕矮。

簡單來說么夫，時間復(fù)雜度指的是語句執(zhí)行次數(shù)，空間復(fù)雜度指的是算法所占的存儲空間肤视。

1档痪、時間復(fù)雜度

（1）時間頻度

一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的邢滑，必須上機(jī)運行測試才能知道腐螟。但我們不可能也沒有必要對每個算法都上機(jī)測試，只需知道哪個算法花費的時間多困后，哪個算法花費的時間少就可以了乐纸。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多摇予，它花費時間就多汽绢。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)侧戴。

（2）時間復(fù)雜度

在剛才提到的時間頻度中宁昭，n稱為問題的規(guī)模，當(dāng)n不斷變化時酗宋，時間頻度T(n)也會不斷變化积仗。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此蜕猫，我們引入時間復(fù)雜度概念寂曹。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)丹锹，用T(n)表示稀颁，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時芬失，T(n)/f(n)的極限值為不等于零的常數(shù)楣黍，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時間復(fù)雜度棱烂，簡稱時間復(fù)雜度租漂。

并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多颊糜，它花費時間就多哩治。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)衬鱼。

⑴ 找出算法中的基本語句业筏；

算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體鸟赫。

⑵ 計算基本語句的執(zhí)行次數(shù)的數(shù)量級蒜胖；

只需計算基本語句執(zhí)行次數(shù)的數(shù)量級消别，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)台谢。這樣能夠簡化算法分析寻狂，并且使注意力集中在最重要的一點上：增長率。

⑶ 用大Ο記號表示算法的時間性能朋沮。

將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中蛇券。

如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體樊拓，如果算法中包含并列的循環(huán)纠亚，則將并列循環(huán)的時間復(fù)雜度相加。

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

     x++;  

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

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

     x++;  

第一個for循環(huán)的時間復(fù)雜度為Ο(n)筋夏，第二個for循環(huán)的時間復(fù)雜度為Ο(n2)菜枷，則整個算法的時間復(fù)雜度為Ο(n+n2)=Ο(n2)。

Ο(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)叁丧，一般來說啤誊，只要算法中不存在循環(huán)語句，其時間復(fù)雜度就是Ο(1)拥娄。其中Ο(log2n)蚊锹、Ο(n)、 Ο(nlog2n)稚瘾、Ο(n2)和Ο(n3)稱為多項式時間牡昆，而Ο(2n)和Ο(n!)稱為指數(shù)時間。計算機(jī)科學(xué)家普遍認(rèn)為前者（即多項式時間復(fù)雜度的算法）是有效算法摊欠，把這類問題稱為P（Polynomial,多項式）類問題丢烘，而把后者（即指數(shù)時間復(fù)雜度的算法）稱為NP（Non-Deterministic Polynomial, 非確定多項式）問題。

（4）在計算算法時間復(fù)雜度時有以下幾個簡單的程序分析法則:

(1).對于一些簡單的輸入輸出語句或賦值語句,近似認(rèn)為需要O(1)時間

(2).對于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時間可采用大O下"求和法則"

求和法則:是指若算法的2個部分時間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))

特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))

(3).對于選擇結(jié)構(gòu),如if語句,它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

(4).對于循環(huán)結(jié)構(gòu),循環(huán)語句的運行時間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費,一般可用大O下"乘法法則"

乘法法則: 是指若算法的2個部分時間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則T1 * T2=O(f(n) * g(n))

(5).對于復(fù)雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術(shù)整個算法的時間復(fù)雜度

另外還有以下2個運算法則:(1)若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))些椒；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數(shù)

（5）下面分別對幾個常見的時間復(fù)雜度進(jìn)行示例說明：

(1)播瞳、O(1)

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

以上三條單個語句的頻度均為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)免糕。算法的時間復(fù)雜度為常數(shù)階赢乓，記作T(n)=O(1)。注意：如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長石窑，即使算法中有上千條語句牌芋，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是O(1)松逊。

(2)躺屁、O(n2)

2.1. 交換i和j的內(nèi)容

sum=0；                 （一次）  

  for(i=1;i<=n;i++)     （n+1次）  

 for(j=1;j<=n;j++) （n2次）  

  sum++经宏；            （n2次）  

解：因為Θ(2n2+n+1)=n2（Θ即：去低階項犀暑，去掉常數(shù)項熄捍，去掉高階項的常參得到），所以T(n)= =O(n2)母怜；

2.2.

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)=2**n2**-n-1
      f(n)=2**n2**-n-1+(n-1)=2**n2**-2余耽；
      又**Θ(2n2-2)=n2**
      該程序的時間復(fù)雜度T(n)=O(**n2**).  

一般情況下，對步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)苹熏，忽略該語句中步長加1碟贾、終值判別、控制轉(zhuǎn)移等成分轨域，當(dāng)有若干個循環(huán)語句時袱耽，算法的時間復(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)<=**log2n**    
      取最大值f(n)=**log2n**,
      T(n)=O(**log2n** )

(5)、O(n3)

for(i=0;i<n;i++)   {        

  for(j=0;j<i;j++)      {  

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

解：

當(dāng)i=m, j=k的時候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時, j 可以取 0,1,...,m-1 , 
 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 
則循環(huán)共進(jìn)行了:  0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時間復(fù)雜度為    O(n3).

（5）常用的算法的時間復(fù)雜度和空間復(fù)雜度

一個經(jīng)驗規(guī)則：其中c是一個常量必峰，如果一個算法的復(fù)雜度為c 洪唐、 log2n 、n 吼蚁、 nlog2n ,那么這個算法時間效率比較高 凭需，如果是2n* ,3n ,n!，那么稍微大一些的n就會令這個算法不能動了肝匆，居于中間的幾個則差強(qiáng)人意粒蜈。

? 算法時間復(fù)雜度分析是一個很重要的問題，任何一個程序員都應(yīng)該熟練掌握其概念和基本方法旗国，而且要善于從數(shù)學(xué)層面上探尋其本質(zhì)枯怖，才能準(zhǔn)確理解其內(nèi)涵。

2粗仓、算法的空間復(fù)雜度

? 類似于時間復(fù)雜度的討論嫁怀，一個算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)借浊。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。

空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度萝招。一個算法在計算機(jī)存儲器上所占用的存儲空間蚂斤，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面槐沼。

算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的曙蒸，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的捌治，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比纽窟，要壓縮這方面的存儲空間肖油，就必須編寫出較短的算法。

算法在運行過程中臨時占用的存儲空間隨算法的不同而異臂港，有的算法只需要占用少量的臨時工作單元森枪，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地"進(jìn)行的审孽，是節(jié)省存儲的算法县袱，如這一節(jié)介紹過的幾個算法都是如此；

有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關(guān)佑力，它隨著n的增大而增大式散，當(dāng)n較大時，將占用較多的存儲單元打颤，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況暴拄。

如當(dāng)一個算法的空間復(fù)雜度為一個常量，即不隨被處理數(shù)據(jù)量n的大小而改變時编饺，可表示為O(1)揍移；當(dāng)一個算法的空間復(fù)雜度與以2為底的n的對數(shù)成正比時，可表示為O(log2n)反肋；當(dāng)一個算法的空I司復(fù)雜度與n成線性比例關(guān)系時那伐，可表示為O(n).

【1】如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句石蔗，其執(zhí)行時間也不過是一個較大的常數(shù)罕邀。此類算法的時間復(fù)雜度是O(1)。

x=91; y=100;
while(y>0) if(x>100) {x=x-10;y--;} else x++;

解答：
T(n)=O(1)养距，
這個程序看起來有點嚇人诉探，總共循環(huán)運行了1100次，但是我們看到n沒有?
沒棍厌。這段程序的運行是和n無關(guān)的肾胯，
就算它再循環(huán)一萬年，我們也不管他耘纱，只是一個常數(shù)階的函數(shù)

【2】當(dāng)有若干個循環(huán)語句時敬肚，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。

x=1; 

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

?        for(j=1;j<=i;j++)

?           for(k=1;k<=j;k++)

?               x++; 　　

該程序段中頻度最大的語句是(5)束析，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關(guān)系艳馒，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：
則該程序段的時間復(fù)雜度為T(n)=O(n3/6+低次項)=O(n3)

【3】算法的時間復(fù)雜度不僅僅依賴于問題的規(guī)模弄慰，還與輸入實例的初始狀態(tài)有關(guān)第美。

在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下：

i=n-1;            

while(i>=0&&(A[i]!=k))       

?      i--;        

return i;  

此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值及K的取值有關(guān):

• ①若A中沒有與K相等的元素陆爽，則語句(3)的頻度f(n)=n什往；
• ②若A的最后一個元素等于K,則語句(3)的頻度f(n)是常數(shù)0。

（5）時間復(fù)雜度評價性能

有兩個算法A1和A2求解同一問題慌闭，時間復(fù)雜度分別是T1(n)=100n2别威，T2(n)=5n3。
（1）當(dāng)輸入量n＜20時贡必，有T1(n)＞T2(n)兔港，后者花費的時間較少。
（2）隨著問題規(guī)模n的增大仔拟，兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大衫樊。
即當(dāng)問題規(guī)模較大時，算法A1比算法A2要有效地多利花。它們的漸近時間復(fù)雜度O(n2)和O(n3)從宏觀上評價了這兩個算法在時間方面的質(zhì)量科侈。

在算法分析時，往往對算法的時間復(fù)雜度和漸近時間復(fù)雜度不予區(qū)分炒事，而經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n))簡稱為時間復(fù)雜度臀栈，其中的f(n)一般是算法中頻度最大的語句頻度。

其實生活很美好挠乳，只是你想的太多了权薯。沒有，不會睡扬，有差距很正常盟蚣，因為我不會