演演算法複雜度

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

（1）時間頻度

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

（2）時間複雜度

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

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

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

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

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

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

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

演演算法的時間性能分析

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

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

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

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

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

求兩個n階方陣的乘積 ,其演演算法如下:

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

分析：

語句(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趨向無窮大時，顯然有;

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

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

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

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

交換i和j的內容。

;

;

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

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

變數計數之一：

(1);;

(2)

(3) x++;

(4)

(5)

(6) y++;

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

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

變數計數之二：

(1);

(2)

(3)

(4)

(5) x++;

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

則該程序段的時間複雜度為。

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

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

(1);

(2)while

(3) i--;

(4)return i;

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

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

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

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

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

• 演演算法程序所佔的空間；

• 輸入的初始數據所佔的存儲空間；

• 演演算法執行過程中所需要的額外空間。

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

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

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