網頁

2018/12/22

演算法 時間複雜度Big O的推論

要分析一個演算法的效率必須推論其時間複雜度Big O,而推論Big O的方法如下。

  1. 用1取代算法中的加法常數。
  2. 只保留最高項次。
  3. 去除與最高項次相乘的常數。

經過以上步驟的結果即為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)。


參考:

沒有留言:

張貼留言