算法複雜度

算法複雜度是指算法在編寫成可執行程式後，運行時所需要的資源，資源包括時間資源和記憶體資源。套用於數學和計算機導論。

基本介紹

• 中文名：算法複雜度
• 外文名：Algorithmic Complexity
• 影響：效率
• 分類：時間複雜度和空間複雜度
• 關鍵：輸入量
• 相關：時間複雜度
• 套用：數學,計算機導論

簡介

同一問題可用不同算法解決，而一個算法的質量優劣將影響到算法乃至程式的效率。算法分析的目的在於選擇合適算法和改進算法。一個算法的評價主要從時間複雜度和空間複雜度來考慮。

時間複雜度

（1）時間頻度

一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。並且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。算法的時間複雜度是指執行算法所需要的計算工作量。

（2）時間複雜度

在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間複雜度概念。

一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函式，用T(n)表示，若有某個輔助函式f(n),存在一個正常數c使得fn*c>=T(n)恆成立。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。

在各種不同算法中，若算法中語句執行次數為一個常數，則時間複雜度為O(1),另外，在時間頻度不相同時，時間複雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間複雜度相同，都為O(n^2)。

按數量級遞增排列，常見的時間複雜度有：

常數階O(1),對數階O(log2n)(以2為底n的對數，下同),線性階O(n),

線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低。

算法的時間性能分析

（1）算法耗費的時間和語句頻度

一個算法所耗費的時間=算法中每條語句的執行時間之和

每條語句的執行時間=語句的執行次數(即頻度(Frequency Count))×語句執行一次所需時間

算法轉換為程式後，每條語句執行一次所需的時間取決於機器的指令性能、速度以及編譯所產生的代碼質量等難以確定的因素。

若要獨立於機器的軟、硬體系統來分析算法的時間耗費，則設每條語句執行一次所需的時間均是單位時間，一個算法的時間耗費就是該算法中所有語句的頻度之和。

求兩個n階方陣的乘積 C=A×B,其算法如下:

# define n 100 // n 可根據需要定義,這裡假定為100void MatrixMultiply(int A[n][n]，int B [n][n]，int C[n][n]){ //右邊列為各語句的頻度    int i ,j ,k;    for(i=0; i<n;i++) //n    for (j=0;j<n;j++) { //n*n        C[i][j]=0; //n2        for (k=0; k<n; k++) //n2*n        C[i][j]=C[i][j]+A[i][k]*B[k][j];//n3    }}

該算法中所有語句的頻度之和(即算法的時間耗費)為：

T(n)=2n³+3n²+2n+1

分析：

語句(1)的循環控制變數i要增加到n，測試到i=n成立才會終止。故它的頻度是n+1。但是它的循環體卻只能執行n次。語句(2)作為語句(1)循環體內的語句應該執行n次，但語句(2)本身要執行n+1次，所以語句(2)的頻度是n(n+1)。同理可得語句(3)，(4)和(5)的頻度分別是n²，n²(n+1)和n³。

算法MatrixMultiply的時間耗費T(n)是矩陣階數n的函式。

（2）問題規模和算法的時間複雜度

算法求解問題的輸入量稱為問題的規模(Size),一般用一個整數表示。

矩陣乘積問題的規模是矩陣的階數。

一個圖論問題的規模則是圖中的頂點數或邊數。

一個算法的時間複雜度(Time Complexity, 也稱時間複雜性)T(n)是該算法的時間耗費，是該算法所求解問題規模n的函式。當問題的規模n趨向無窮大時，時間複雜度T(n)的數量級(階)稱為算法的漸進時間複雜度。

算法MatrixMultiply的時間複雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有T(n)~O(n^3);

這表明，當n充分大時，T(n)和n^3之比是一個不等於零的常數。即T(n)和n^3是同階的，或者說T(n)和n^3的數量級相同。記作T(n)=O(n^3)是算法MatrixMultiply的漸近時間複雜度。

（3）漸進時間複雜度評價算法時間性能

主要用算法時間複雜度的數量級(即算法的漸近時間複雜度)評價一個算法的時間性能。

算法MatrixMultiply的時間複雜度一般為T(n)=O(n^3)，f(n)=n^3是該算法中語句(5)的頻度。下面再舉例說明如何求算法的時間複雜度。

交換i和j的內容。

Temp=i;

i=j;

j=temp;

以上三條單個語句的頻度均為1，該程式段的執行時間是一個與問題規模n無關的常數。算法的時間複雜度為常數階，記作T(n)=O(1)。

注意：如果算法的執行時間不隨著問題規模n的增加而增長，即使算法中有上千條語句，其執行時間也不過是一個較大的常數。此類算法的時間複雜度是O(1)。

變數計數之一：

(1) x=0;y=0;

(2) for(k=1;k<=n;k++)

(3) x++;

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

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

(6) y++;

一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分。因此，以上程式段中頻度最大的語句是(6)，其頻度為f(n)=n^2，所以該程式段的時間複雜度為T(n)=O(n^2)。

當有若干個循環語句時，算法的時間複雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

變數計數之二：

(1) x=1;

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

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

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

(5) x++;

該程式段中頻度最大的語句是(5)，內循環的執行次數雖然與問題規模n沒有直接關係，但是卻與外層循環的變數取值有關，而最外層循環的次數直接與n有關，因此可以從內層循環向外層分析語句(5)的執行次數：

則該程式段的時間複雜度為T(n)=O(n^3/6+低次項)=O(n^3)。

（4）算法的時間複雜度不僅僅依賴於問題的規模，還與輸入實例的初始狀態有關。

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

(1)i=n-1;

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

(3) i--;

(4)return i;

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

①若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n；

②若A的最後一個元素等於K,則語句(3)的頻度f(n)是常數0。

空間複雜度

與時間複雜度類似，空間複雜度是指算法在計算機內執行時所需存儲空間的度量。記作:

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

算法執行期間所需要的存儲空間包括3個部分：

• 算法程式所占的空間；
• 輸入的初始數據所占的存儲空間；
• 算法執行過程中所需要的額外空間。

在許多實際問題中，為了減少算法所占的存儲空間，通常採用壓縮存儲技術。

複雜度分析

通常一個算法的複雜度是由其輸入量決定的，隨著輸入的增加，不同算法的複雜度增長速度如右圖所示：

複雜度

為了降低算法複雜度，應當同時考慮到輸入量，設計較好的算法。