演算法-資料結構學習筆記 BIG O Notation
前言
在解釋何為 BIG O 之前，我們必須先聊聊它的背景，以及它想要解決的困境。
試著想像一下，假設今天要實作某個複雜的功能，十位工程師可能會有十種寫法，但我們有沒有一種公正客觀的方式可以檢驗程式碼的效率或品質呢？
第一個想到的可能會是時間，只要計算完成該功能或函式耗費的時間，並且找出費時最小的寫法就行了吧？
但即使是同一段程式碼，在不同的作業環境、硬體規格上運行時，也可能會有截然不同的耗費時間，因此純粹計算時間不能說是準確的檢驗方式。
另一種方式則是計算程式碼有多少運算子，例如加號、乘號或比大小…等。然而這樣的做法也有個問題，就是計算上非常麻煩；此外，如果運算次數的差異比較小，像是 5n + 3 和 5n 的運算次數，可能也會出現 5n 比 5n + 3 還慢的情況，尤其是在不同電腦上執行時。
因此，我們要介紹一種目前常用於表達程式碼時間複雜度的符號：BIG O。
什麼是 BIG O Notation
本次要介紹的概念 BIG O 就是判斷程式碼品質的重要依據之一，是接下來進入演算法世界的必備知識，我們需要使用 BIG O 來顯示程式碼的時間複雜度或空間複雜度，讓他人可以一眼就看懂某一段程式碼的效率，以及是否有改進的空間。
時間複雜度計算方式
我們首先來看比較常使用到的時間複雜度。
BIG O 會記下運算中最大次方的項數，並且忽略其他係數，假設是上述提到的 5n + 3，就會記為 O(n)。
雖然省去了準確且詳細的計算結果，但依然表達了複雜度的趨勢，因為對程式碼的運算效率而言，次方數的提升影響較為重大。
我們用下列兩個函式來舉例，兩者要實作的功能是回傳 1 ~ n 之間每個整數的相加結果。
function addUpToFirst(n) {
var total = 0;
for (var i = 0; i <= n; i++) {
total += i;
}
return total;
}- addUpToFirst() 的運算子次數最高為 n，因此 BIG O 就會記為 O(n)
function addUpToSecond(n) {
return n * (n + 1) / 2;
}- addUpToSecond() 的運算子次數最高為常數項，因此 BIG O 就會記為 O(1)
不過，萬一遇到步驟的次方數會依據情況而變化的程式碼呢？我們來看看這個例子：
function logAtLeast5(n) {
for (let i = 0; i <= Math.max(5, n); i++) {
console.log(i)
}
}在上述的程式碼當中，只要代入的參數小於等於 5，該函式就會印出 1 ~ 5，時間複雜度為 O(1)
但如果大於 5，該函式就會印出 1 ~ n，時間複雜度為 O(n)
在計算時間複雜度時，我們一律要考量最壞的情況，因為在沒有限制的情況下，函式可能會代入 10000000 這樣的數字，因此這個函式的時間複雜度依然要記為 O(n) 而非 O(1)
當我們計算出時間複雜度後，就可以去思考如何改進，以上圖為例，通常我們會希望時間複雜度的次方數越低越好，假如是 n² 的話，就會希望可以減少至 n，或更低的 O(log n) / O(1)。
最後，總結一下 BIG O 的幾項重點：
- BIG O 是計算程式碼的步驟次數，而非耗費時間
- BIG O 只記錄步驟次數的最高次方項，假設步驟次數為 n + 3，記為 O(n)，而非 O(n + 3)
- BIG O 一律省略係數，假設步驟次數為 5n，記為 O(n)，而非 O(5n)
- BIG O 一律考量最壞情況的步驟次數
BIG O 與空間複雜度
相較於運算時間，耗費多少記憶體容量也是判斷程式碼好壞的依據之一，而 BIG O 其實也可以用來計算空間的複雜度。
以 JS 為例，各型別的計算方式如下：
- 常數項：number, undefined, null, boolean
- n 項：array (length), object (key-value pairs), string
我們再用兩個函式來舉例，一個是在上一段時間複雜度使用過的範例，另一個則是代入一個陣列，並逐一印出所有的元素
function addUpToSecond(n) {
return n * (n + 1) / 2;
}- 因為只有使用到 n 這個參數，空間複雜度的 BIG O 為 O(1)
function logArray(arr) {
for (let i = 0; i < arr.length; i++) {
console.log(arr[i])
}
}- 由於參數是一個陣列，因此空間複雜度的 BIG O 為 O(n)
JS Arrays and Objects
稍微了解了 BIG O 後，趕緊打鐵趁熱來看一下寫 JS 時常用的陣列與物件方法吧！
在 JS 中，物件與陣列最大的差別就在於排序的有無，當我們要在物件中新增、移除一對 key 與 value，或是藉由 key 取得對應的 value 時，時間複雜度都會是 O(1)。
不過，假設我們要使用 JS Objects method，像是 Object.entries() / Object.keys() / Object.values() 取得物件的 key value pair / 所有屬性 / 所有值時，由於它們必須迭代整個物件，並且回傳一個陣列，因此時間複雜度會是 O(n)。
接著來看看陣列，JS 的陣列提供了兩種新增與移除的方法，分別是從陣列的頭或尾部插入、移除元素。乍看之下，這只是位置的差別而已，但從 BIG O 的角度來看，卻差別很大。
首先，由於陣列是具有順序的，每個元素都會有一個 index 代表其在陣列中的位置，以下用一個包含3 個人名的陣列舉例：
['Bobby', 'Cathy', 'Zoe']// 0 1 2 (index 值)
假設我們今天在上述的陣列尾部插入一個新的人名：Teddy
['Bobby', 'Cathy', 'Zoe', 'Teddy']// 0 1 2 3 (index 值)
可以發現，陣列的前三個元素不會被更動，只要加上 Teddy 本身即可，從尾部移除元素也是同理。因此，這裡的時間複雜度會是 O(1)
那如果從頭部新增或移除呢？
['Teddy', 'Bobby', 'Cathy', 'Zoe']// 0 1 2 3 (index 值)
可以看到，由於 JS 陣列的第一個元素 index 值必須為 0，因此原本就存在陣列中的三個元素，就得因為新插入的元素而變更 index 值，從頭部移除時也是同樣的道理。在這種情況下，時間複雜度就會提升至 O(n) 了
而其他常見的陣列方法，像是 forEach, slice, concat, map, filter … 等，時間複雜度也都是 O(n)。
最後總結一下，從 BIG O 分析時間複雜度的角度，可以幫助我們理解演算法的效能，從而依據情況選擇適當的方法，或是找到改進的方向。
面對 JS 的物件與陣列時，比起看心情來使用，也可以從時間複雜度的角度和情境去思考，如果今天不需要特別排序資料，或是資料本身的差異性很高，那麼使用物件來儲存資料，通常就會是個比陣列更好的選擇。
