[工程師基礎知識]2. 時間複雜度是什麼？

最近令我震驚的一件事就是「並非所有職業工程師都會有時間複雜度觀念」，所以「我懂時間複雜度」這件事說不定在面試時也是一件能說嘴的事呢。

時間複雜度（Time Complexity）是一種描述演算法運算時間如何隨著輸入資料量的增加而變化的度量標準。

它通常以大 "O" 符號表示，這被稱為 "O 標記法" 或 "O(n) 標記法"。在這裡，"n" 通常表示輸入數據的大小。

以下是一些常見的時間複雜度範例：

O(1): 常數時間複雜度。無論輸入數據的大小如何，運行時間都保持不變。例如一般的key-value儲存結構，HashMap。

O(n): 線性時間複雜度。運行時間與輸入數據的大小成正比。例如for迴圈。

O(log n): 對數時間複雜度。每次操作都可以在一定比例上減少未處理的輸入數據的大小。例如猜數字，每次猜的時候排除一半的可能，1～100猜中任意數字的次數最多7次。

O(n^2): 平方時間複雜度。如果輸入數據的大小翻倍，那麼運行時間將會變為原來的四倍。例如兩層迴圈，可以想見三層迴圈就可能變為O(n^3)。

O(2^n) 和 O(n!): 指數時間複雜度和階乘時間複雜度。這些演算法的運行時間隨著輸入數據的大小而急劇增加，通常只對非常小的輸入規模有效。我沒有碰過這類的實際案例。

時間複雜度是衡量演算法效率的重要工具，它可以幫助我們預測和控制演算法的運行時間。然而，不應忽視其它的效能因素，如空間複雜度、網路延遲、磁碟 I/O 等。

其實除了`O`之外還有其他符號，不過日常會用到的應該就只有O了。

O的意思是符合某個數量級，因此會省略常數的部分，O(2n) 會記為 O(n)。

「不是所有人都會」反過來說，不會時間複雜度也能在業界活下去，那麼學會時間複雜度有什麼用呢？

• 讓自己寫出更好的程式（自我提升）

• 維持自己出品程式的口碑

• 幫助自己更有機會進入更注重程式品質的公司

• 減少讓程式掛掉的可能（被緊急呼叫修程式真的很累）

• 避免被後續維護的同行怨恨（我們真的沒那麼需要被製造這種工作機會！）

實務開發注意事項

如果資料量不會持續增加，可以為了可讀性使用效能較差的演算法

• 但是前提是資料量真的少，而且用好的演算法真的不好讀。

雖然時間複雜度表示的時候會省略常數，但是實務上開發的時候應該要減少常數，也就是減少重複計算/重複處理的部分，也會有明顯體感差異。

舉個例子，某專案有個彙整資料報表，要計算查詢到的n筆原始資料中分別被記錄到3個計數欄位（性別是男性女性或不詳），效能比較差的方式是這樣：

女性count = 0;
檢查每筆資料(n)
  如果sexId是女性，女性count + 1

男性count = 0;
檢查每筆資料(n)
  如果sexId是男性，男性count + 1

不詳count = 0;
檢查每筆資料(n)
  如果sexId不是男性也不是女性，不詳count + 1

如此取得了三個計數值

這做法複雜度是O(n)，但是跑了三次n，其中應該也可看出，第三次是多餘的，只要把總數－女性－男性就可以得到答案。

但我們先維持原本的邏輯，換成比較有效率的寫法：

女性count = 0;
男性count = 0;
不詳count = 0;

檢查每筆資料(n)
  如果sexId是女性，女性count + 1
  否則 如果sexId是男性，男性count + 1
  否則 不詳count+1

如此取得了三個計數值

這寫法可以對每筆資料只判斷一次，不只效能提升，也可以增加可讀性。

※：這是真實案例改編，不是我故意準備的低級錯誤，而且案例的重複迴圈不是3個，是110個。

可以為了可讀性使用效能較差的演算法？

延續上面的例子，有另外三個欄位要記錄「65歲以下，65歲以上，不詳」的數量，追求效率的情況我應該這樣寫：

女性count = 0;
男性count = 0;
不詳count = 0;
65歲以下count = 0;
65歲以上count = 0;
年齡不詳count = 0;

檢查每筆資料(n)
  如果sexId是女性，女性count + 1
  否則 如果sexId是男性，男性count + 1
  否則 不詳count+1

  如果缺少age欄位，年齡不詳count + 1
  否則 如果age小於65，65歲以下count + 1
  否則 65歲以上count + 1

如此取得了所有計數值

這個寫法本身不難看，不過有人會比較喜歡下面這種寫法：

// 計算性別數值
女性count = 0;
男性count = 0;
不詳count = 0;

檢查每筆資料(n)
  如果sexId是女性，女性count + 1
  否則 如果sexId是男性，男性count + 1
  否則 不詳count+1

// 計算年齡數值
65歲以下count = 0;
65歲以上count = 0;
年齡不詳count = 0;

檢查每筆資料(n)
  如果缺少age欄位，年齡不詳count + 1
  否則 如果age小於65，65歲以下count + 1
  否則 65歲以上count + 1

如此取得了所有計數值

分成兩次迴圈讀取同樣的資料，分別計算不同組別的數值，尤其是分別的邏輯更加複雜的時候更可能有人如此選擇。

也許是為了方便分開測試，而複雜度同樣維持在O(n)而只差常數的情況，如此使用確實無不可。

用儲存結構整理資料利於使用

不論原始資料是如何取得的，為了降低複雜度可以考慮用其他方式整理資料。

當你為了查詢案件報表的資料，分別得到了一個人員名單(m筆)和一個案件名單(n筆)，要產生n筆報表資料對應n筆案件，並且每筆案件要根據案件上的userID取得人員姓名。

首先為了準備每筆案件的報表資料，時間複雜度至少是O(n)，如果每筆資料取得姓名都要從人員名單找一次對應的姓名，時間複雜度就會是O(n*m)，也就是O(n^2)。

但是如果先跑一次迴圈把人員名單整理成userID對應姓名的人員對應表(Map)，每筆資料要取得姓名時改為用userID換得姓名的用法，就可以適用Map讀寫效率O(1)的優點，如此時間複雜度就會減為O(m + n*1)，也就是O(n)。

想像一下上面的例子，如果還有另一組來電名單需要用案件ID取得來電名單上的來電號碼，一不小心就會變成O(n^3)的複雜度了。

有時資料來源很多，或是資料量很大的情況，光是少了這個預處理就可以讓處理時間爆增不少，當n=13萬，m=18萬的情況（真實案例），讀取資料的次數會差多少呢？