時間複雜度 – 陪你刷題

為什麼要學 Big O

學習演算法和資料結構就是為了寫出高效率的程式碼,不只在時間上需要快速,在空間上的消耗更要節省,而 Big O 就是用來衡量演算法效率的單位。因此,在學習各種資料結構與演算法帶來的好處之前,要先懂得如何透過 Big O 辨別程式碼的效率。

時間複雜度

時間複雜度也稱為漸進執行時間 (asymptotic runtime) ,用來表達隨著資料規模的變大,執行時間如何放大。 在計算複雜度時,不用執著於最精準的執行時間,細節需要考慮到組合語言層次與編譯器等問題,這樣做太複雜,我們只需要接受 O(N) 一定比 O(N^2) 好。


資料來源:https://www.bigocheatsheet.com/

計算時間複雜度步驟

  1. 只關心最壞的情況 (業界對時間複雜度的使用方式:對執行時間以最緊的標準來描述。)
  2. 移除常數
    Big O 只描述增加的速率,因此可以降低執行時間的常數,描述為 O(2N^2) 的演算法實際上表示為 O(N^2) 即可。
  3. 降低非優勢條件
    像 O(N^2 + N) ,第二個 N 完全不重要,在移除常數說過,O(N^2 + N^2) 可視為 O(N^2) ,竟然後面 N^2 都不在乎了,這邊的 N 也可以完全捨去。

    • O (N + logN) 變成 O (N)
    • O (3* 2^N + 1000 * N^100) 變成 O (2^N)
  4. 多步驟演算法:加與乘
    假設演算法有兩個步驟,什麼時候相加或相乘執行時間呢?
for (int i : A)
    print i;
for (int j : B)
    print j;
for (int i : A)
    for (int j : B)
        print i + j;

上方程式是先執行 A 再執行 B ,因此時間複雜度為 O (A+B) 。
下方程式每次執行一次 A ,會再執行一次 B ,因此時間複雜度為 O (A * B)

可以歸納為

  • 若形式為 "先做這個,完成後,做另外一個" ,則執行時間相加。
  • 若形式為 "每次做這個時候也做那個" ,則執行時間相乘。

log N 執行時間

  • 當你看到題目中元素的數量每次折半,他很可能是 O(log N) 執行時間。

  • 對數底對 Big O 不重要,不同底的對數造成的差別為常數係數。

遞迴執行時間

int f(int n) {
    if (n<=1) {
        return 1;
    }
    return f(n-1) + f(n-1);

許多人看到有兩個 f(n) 的呼叫,就認為是 O(n^2) ,這不是對的。

實際走一遍程式碼,你會發現整個執行過程如同二元樹,每次呼叫遞迴函式會再呼叫兩個遞迴函式,就如同一個節點會有兩個子節點。 因此,每一層都比上一層多一倍呼叫。

嘗試記住這個表! 遇到遞迴函式時,執行時間通常看起來像 O (分支 ^ 深度) ,分支為每個遞迴呼叫再次呼叫的數量,因此,這個遞迴函式時間複雜度為 O (2^n) 。

範例 1

假設有個演算法將字串陣列的每個字串排序後再排序整個陣列,執行時間是什麼?

很多人會這麼看:字串排序是 O(N log N) ,每個字串都要執行,因此是 O(N * N log N) 。 我們還需要排序陣列,因此還要一個 O ( N log N) 。所有全部執行時間為 O ( N^2 log N + N Log N) ,也就是 O ( N^2 log N ) 。

以上說法完全錯誤!

第一個錯誤,不能以 N 來表達兩個不一樣的長度,一個是字串的長度,一個是字串陣列內的字串數量,面試時,記得要清楚定義你的 N 。

讓我們清楚定義長度,並給予合理的名稱。

  1. 以 s 作為最長字串的長度。
  2. 以 a 作為字串陣列內字串數量。

接下來可以這樣計算:

  • 對單一字串排序所需時間為 O ( s log s ) ,總共有 a 個字串,因此所有的字串需要 O (a * s log s) 。
  • 對所有字串排序,因為有 a 個字串,排序所有字串要花時間為 O ( a log a ) 時間。但是還要考慮到字串比較時,字串內的每個字元可能還需要進一步比較,又需要 O (s) 的時間,因此總共需要花 O (s * a log a) 時間。

整個過程需要上面兩個時間複雜度相加 O (a * s * (log a + log s) ) 。

空間複雜度

空間複雜度也稱為 asymptotic space complexity ,表達隨著資料規模增大,程式所需空間如何增大。

需要計算消耗空間的因素有:

  1. 變數
  2. 資料結構的使用
  3. Function call
  4. 記憶體配置

需特別注意,遞迴呼叫所需的堆疊 ( stack ) 空間也需要計算。下面程式需要 O(n) 的時間與 O(n) 的空間。

int sum (int n) {
    if (n <= 0) {
        return 0;
    }
    return n * sum (n-1);
}

參考

  1. Cracking the coding Interview 6th edition chapter VI
  2. https://www.bigocheatsheet.com/