演算法 時間複雜度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(n²)。

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(n²)。

參考：

• 大話資料結構 - 程杰(ISBN 978-986-6072-11-6)
• 演算法 常見的時間複雜度所需的時間排列