【資料結構與演算法】- Big O Notation

【資料結構與演算法】- Big O Notation

Big O Notation 是一種工具：假設有個函式 f(n) 當 input 值放大時 n 的上升曲線大小就是由 Big O Notation 評斷。

考慮最糟糕的情況，當 input size 龐大時複雜度的成長趨勢

Big O 算法規則：

1. 常數不重要( Constants doesn’t matter )

2. 取最大值 ( Small Terms don’t matter )

3. log底數不重要 ( Logarithm Base doesn’t matter )

常見的 Big O 演算法( 好到差 )：

1. O(1)

2. O(logn)

3. O(n)：最常見的

4. O(nlogn)：使用 sorting

5. O(n²)：想辦法變成 3 or 4。

6. O(n³)：想辦法變成 3 or 4。

最理想的狀態是使用 O(1) 和 O(logn)，O(n) 是比較常見的 case，大多 sorting 演算法 Big O 的值都是 O(nlogn)，如果有 O(n²)、或O(n³)要想辦法變成 O(n) 或 O(nlogn) 。

Q：假設目前有四個 f(n)，這裡可能就會有個疑問是， 1500 也會影響到演算法的速度，為何 f3(n) 的 Big O 值可以直接去掉 1500 呢 ?

1. f1(n) = 1000 — — — — → O(1)

2. f2(n) = n — — — — —→ O(n)

3. f3(n) = n + 1500 — —→ O(n)

4. f4(n) = n² — — — — — → O(n²)

看下表就可以知道，當在 input 值 = 1 時 f1(n) 和 f3(n) 這兩個演算法花費時間明顯大於其他兩種。不過當 input 值提升到 100 時， f4(n) 花費的時間遠遠大於其他幾種演算法，這也是為什麼要盡量避免使用 f4(n) 這種演算法的理由。最後，當 input 值提升到了100000 時，會發現其實 f2(n) 和 f3(n) 花費的時間的差距是最相近的，而文章開頭有介紹到，Big O Notation 考慮的是最糟糕的情況( worst case scenario )，在這個例子中就是 input 值 = 100000，這也是為什麼 Big O Notation 會忽略 1500 的原因。

了解了 Big O Notation 的定義和概念後，接著就來看看原生的 JavaScript 中Array 和 Objcet 的各種方法分別屬於哪種 Big O Notation 吧 !!

這些方法的功能不外乎就是四種

1. 新增 Insertion

2. 移除 Removal

3. 搜尋 Seaching

4. 取值 Access

先來看看 Object 做以上四種動作時個別的 Big O Notation：

1. Insertion → O(1)：不管 Obj 多大，新增屬性時所耗費的時間都是一樣的

2. Removal ****→ O(1)：同上，刪除屬性時所耗費的時間一樣

3. Seaching → O(n)：從第一個屬性開始找，直到找到為止，花費時間與 Obj 大小成正比

4. Accessing → O(1)：使用 Hash Tables 這種演算法，因此可以達到不管物件大小取值所耗費的時間都相同的效果 。

再來是 Array ：

1. Insertion

• push → O(1)：直接新增在最後新增值，不會影響到原本陣列 index

• unshift→ O(n)：新增第一個 index 的值，會讓後面的 index 都 +1

1. Removal ****→ O(1)：同上，刪除屬性時所耗費的時間一樣

• pop→ O(1)：直接移除最後的值，不會影響到原本陣列 index

• shift→ O(n)：移除第一個 index 的值，會讓後面的 index 都 -1

1. Seaching→ O(n)：從第一個 index 開始找，直到找到為止，花費時間與 Array 長度成正比

2. Accessing→ O(1)：同樣使用 Hash Tables，同樣直接取值。 EX：arr[9] 、 arr[999] 花費時間相同。

EXAMPLE：

後記：荒廢了大概四個月的部落格，因為確診兵役延期才又有時間來整理筆記，恰好寫面時題時發現事情不太對勁，對於資料結構與演算法還有很多不了解的部分，除了這個主題之外也想要整理一下 typeScrtipt 的筆記，希望自己能夠撐過去!!!