要分析一個演算法的效率必須推論其時間複雜度Big O,而推論Big O的方法如下。
- 用1取代算法中的加法常數。
- 只保留最高項次。
- 去除與最高項次相乘的常數。
經過以上步驟的結果即為Big O。
例如計算下面的時間複雜度
for(int i = 0; i < n; i++) {
for(int j = i; j < n ; j++) {
// 時間複雜度O(1)的執行步驟
}
}
注意j=i,所以
當i=0時,內迴圈執行n次,
當i=1時,內迴圈執行n-1次,
當i=2時,內迴圈執行n-2次...
所以全部的執行次數可寫成
n + (n-1) + (n-2) + ... + 1 => n(n + 1)/2 => n2/2 + n/2
---------------------------
n個
依上面推論Big O方法來分析n2/2 + n/2
,
只保留最高次項n2/2
,除去n/2
,
去除相乘的常數1/2
,
所以結果為O(n2)。
n2/2 + n/2
=> n2/2
=> n2 * 1/2
=> n2
比較複雜的情況如下。
n++; // 執行次數為 1
function(n); // 假設執行次數為 n
for(int i = 0; i < n; i++) { // 執行次數為 n2
function(i);
}
for(int i = 0; i < n; i++) { // 執行次數為 n(n+1)/2
for(int j = i; j < n ; j++) {
// 時間複雜度O(1)的執行步驟
}
}
則總共的執行次數為
f(n) = 1 + n + n2 + n2/2 + n/2
去除加法,只考慮最高項次,去除與最高項次相乘的常數,所以結果仍為O(n2)。
參考:
- 大話資料結構 - 程杰(ISBN 978-986-6072-11-6)
- 演算法 常見的時間複雜度所需的時間排列
沒有留言:
張貼留言