如何度量一個算法的效率呢？
一種方法是事後統計的方法，先将算法實作，然後輸入适當的資料運作，測算其時間和空間開銷。
事後統計的方法至少有以下缺點：
① 編寫程式實作算法将花費較多的時間和精力；
② 所得實驗結果依賴于計算機的軟硬體等環境因素，有時容易掩蓋算法本身的優劣。
通常我們采用事前分析估算的方法——漸進複雜度（asymptoticcom-plexity），它是對算法所消耗資源的一種估算方法。
一、算法的時間複雜度
撇開與計算機軟硬體有關的因素，影響算法時間代價的最主要因素是問題規模。
問題規模（problom scope）是指輸入量的多少，一般來說，它可以從問題描述中得到。
一個顯而易見的事實是：
幾乎所有的算法，對于規模更大的輸入需要運作更長的時間。
要精确地表示算法的運作時間函數常常是很困難的，即使能夠給出，也可能是一個相當複雜的函數，函數的求解本身也是相當複雜的。
基本語句（basicstatement）是執行次數與整個算法的執行次數成正比的語句，
基本語句對算法運作時間的貢獻最大，是算法中最重要的操作。
這種衡量效率的方法得出的不是時間量，而是一種增長趨勢的度量。
換言之，隻考查當問題規模充分大時，算法中基本語句的執行次數在漸近意義下的階，稱作算法的漸進時間複雜度，簡稱時間複雜度（timecomplexity），通常用大O（讀作“大歐”）記号表示。
定義1-1 若存在兩個正的常數 c和 n0，對于任意 n ≥ n0，都有 T（n）≤ cf（n），
則稱T（n）= O（f（n））（或稱算法在O（f（n））中）。
該定義說明了函數T（n）和f（n）具有相同的增長趨勢，并且T（n）的增長至多趨同于函數f（n）的增長。大 O記号用來描述增長率的上限，也就是說，當輸入規模為n時，算法耗費時間的最大值，
算法的時間複雜度分析實際上是一種估算技術，若兩個算法中一個總是比另一個“稍快一點”時，它并不能判斷那個“稍快一點”的算法的相對優越性。
但是在實際應用中，它被證明是很有效的，尤其是确定算法是否值得實作的時候。
常見的時間複雜度如下：
算法的時間複雜度是衡量一個算法優劣的重要标準。
一般來說，具有多項式時間複雜度的算法是可接受的、可使用的算法；
而具有指數時間複雜度的算法，隻有當問題規模足夠小的時候才是可使用的算法。
如下給出了多項式增長和指數增長的比較。
二、算法的空間複雜度
算法在運作過程中所需的存儲空間包括：
① 輸入/輸出資料占用的空間；
② 算法本身占用的空間；
③ 執行算法需要的輔助空間。
其中，輸入/輸出資料占用的空間取決于問題，與算法無關；
算法本身占用的空間雖然與算法相關，但一般其大小是固定的。
是以，算法的空間複雜度（spacecomplexity）是指在算法執行過程中所需要的輔助空間數量，也就是除算法本身和輸入/輸出資料所占用的空間外，算法臨時開辟的存儲空間。
如果算法所需的輔助空間相對于問題規模來說是一個常數，我們稱此算法為原地（或就地）工作；
否則，這個輔助空間數量也應該是問題規模的函數，通常記作：
S（n）=O（f（n））
三、算法分析舉例
1. 非遞歸算法的時間性能分析
對非遞歸算法時間複雜度的分析，關鍵是建立一個代表算法運作時間的求和表達式，然後用漸進符号表示這個求和表達式。
示例：
(1) 時間複雜度為 O(1)，稱為常量階.
++x;
(2) 時間複雜度為 O(n)，稱為線性階.
for(int i = 1; i<=n; ++i)
++x
(3) 時間複雜度為 O(n2)，稱為平方階.
for(i = 1; i<=n; i++)
for(j = 1; j<=n; j++)
++x;
(4) 時間複雜度為 O(n3)，稱為立方階.
for(i = 1; i<=n; i++)
for(j = 1; j<=n; j++)
{
c[i][j] = 0;
for( k = 1; k<=n; ++k )
c[i][j] += a[i][k] * b[k][j];
}
(5) 時間複雜度為 O(log_2^n)，稱為對數階
for( i=1; i<=n; i=2*i )
++x;
假設其執行次數為 T(n), 則有 2^T（n）<= n， 即 T（n）≤log_2^n
2. 遞歸算法的時間性能分析
對遞歸算法時間複雜度的分析，關鍵是根據遞歸過程建立遞推關系式，然後求解這個遞推關系式。
通常用擴充遞歸技術将遞推關系式中等式右邊的項根據遞推式進行替換，這稱為擴充，擴充後的項被再次擴充，依此下去，就會得到一個求和表達式。
3. 最好、最壞和平均情況
對于某些算法，即使問題規模相同，如果輸入資料不同，其時間開銷也不同。
此時，就需要分析最好、最壞以及平均情況的時間性能。
例如，順序查找法
int Find( int a[], int n){
for( i = 0; i< n , i ++)
if(a[i] == k) break;
return i;
}
順序查找從第一個元素開始，依次比較每一個元素，直到找到k為止，而一旦找到了k，算法也就結束了。
如果數組的第一個元素恰好就是k，算法隻要比較1次就行了，這是最好情況；
如果數組的最後一個元素是k，算法就要比較n次，這是最壞情況；
如果在數組中查找不同的元素k，假設資料等機率分布，則平均要比較n/2次，這是平均情況。
一般來說，最好情況不能代表算法性能，因為它發生的機率太小，對于條件的考慮太樂觀了。
但是，當最好情況出現的機率較大的時候，應該分析最好情況；