對(duì)于數(shù)據(jù)結(jié)構(gòu)的基本概念我們不做敘述，本節(jié)重點(diǎn)討論算法效率的度量。

性能分析的角度

一般我們從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面對(duì)算法的效率進(jìn)行分析。

一.時(shí)間復(fù)雜度（Time Complexity）

我們通常將時(shí)間復(fù)雜度記為：

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

我們將此式分為三個(gè)部分進(jìn)行講述。

• T(n):算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
• f(n):算法中語(yǔ)句中執(zhí)行次數(shù)最多的語(yǔ)句的頻度。
• O():計(jì)算數(shù)量級(jí)。
  數(shù)學(xué)表達(dá)式為：

存在正常數(shù)C和n0，當(dāng)n>=n0時(shí)，0<=T(n)<=C*f(n)

1.三種時(shí)間復(fù)雜度

• 最壞時(shí)間復(fù)雜度：最壞情況下的時(shí)間復(fù)雜度。
• 平均時(shí)間復(fù)雜度：所有輸入實(shí)例等概率出現(xiàn)情況。
• 最好時(shí)間復(fù)雜度：最好情況下時(shí)間復(fù)雜度。
  我們利用一個(gè)例子說(shuō)明：

在冒泡排序中，如果序列本有序，我們只需比較n-1次，排序完成，則為最好情況下時(shí)間復(fù)雜度為O(n)。如果序列為逆序，則需要比較(n-1)+(n-2)+....+1=n*(n-1)/2，此時(shí)時(shí)間復(fù)雜度為O(n2)。則平均復(fù)雜的也為O(n2)。

2.常見(jiàn)的時(shí)間復(fù)雜度(從小到大排列)

• 常數(shù)階：O(1)
• 對(duì)數(shù)階：O(log2n)

void fun(int n){
  int i=1;
  while(i<=n)
    i=i*2;
}

• 線性階：O(n)

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

• 線性對(duì)數(shù)階：O(nlog2n)

count=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=n;j++)
    count++;

• 平方階：O(n2)

for(int i=0;i<n;i++){
  for(int j=0;j<n;j++)
}

• 立方階：O(n3)

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

• 指數(shù)階：O(2^n)

//Fibonacci數(shù)列的遞歸算法
int f(int n){
  if(n==1||n==0){
     return 1;
}
return f(n-1)+f(n-2);
}

• 階乘：O(n!)
• k次方階：O(n^k)

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

• 循環(huán)條件中變量參與循環(huán)條件

 int i=1;
 while(i<=n){
 i=i*2;
} 

對(duì)于此種程序，我們?cè)O(shè)循環(huán)次數(shù)為t，則可根據(jù)循環(huán)條件得到：

2^t<=n 于是可以推出 t<=log2n,得到T(n)=log2n

• 循環(huán)主體中變量與循環(huán)條件無(wú)關(guān)
  Ⅰ.遞歸程序：利用公式進(jìn)行遞推。
  Ⅱ.非遞歸程序

二.空間復(fù)雜度(Space Complexity)

我們通常將空間復(fù)雜度記為：

S(n)=O(f(n))

我們將此式分為三個(gè)部分進(jìn)行講述。

• S(n)：空間復(fù)雜度。
• f(n)：輔助存儲(chǔ)空間。

輔助存儲(chǔ)空間：
一般情況下, 一個(gè)程序在機(jī)器上執(zhí)行時(shí), 除了需要存儲(chǔ)本身所需要的代碼/輸入數(shù)據(jù)外, 還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的輔助存儲(chǔ)空間.其中輸入數(shù)據(jù)所占用的具體空間取決于問(wèn)題本身, 與算法無(wú)關(guān). 因此我們所討論的空間復(fù)雜度只與該算法在實(shí)現(xiàn)時(shí)所需要的輔助空間單元個(gè)數(shù)相關(guān)

• O()：數(shù)量級(jí)。

1.常見(jiàn)空間復(fù)雜度

• 常數(shù)階 O(1)：冒泡排序，直接插入排序，簡(jiǎn)單選擇排序，希爾排序，堆排序。
• 線性階 O(n)：二路歸并排序。
• 對(duì)數(shù)階 O(log2n)：快速排序。

author by HengGeZhiZou