• 要看一個演算法好不好、運行快不快，就會需要用到 Big O notaion

    • 運行得快不快 → 時間複雜度

    • 消耗多少的電腦記憶體空間 → 空間複雜度

  • Big O notaion 是一個數學符號，可以拿來表示時間複雜度或是空間複雜度

  • 如果兩種演算法都能做一樣的事情，只是做法不同而已的話，有差異的部分是時間、空間

    • 比如加法到 n 有兩種方式，一種是 For 迴圈，一種是公式解

  • 關於怎麼判斷演算法好壞，無非就是執行速度，或是占用記憶體多寡

    • 一般沒有學過演算法的人很難看出來

  • 大家在意的是時間跟空間

  • f(n) → f of n 來表示

  • 時間複雜度可能會隨著 n 增加更多

  • 可以理解成運行幾次

我想要透過研究及學習釐清的困惑點：

  1. 演算法這個詞是什麼意思？

  2. 為什麼要用 Big O？

  3. 了解 Complexlty 的幫助

演算法這個詞是什麼意思？

定義：step-by-step procedure to solve a problem。

意思是說只要一步一步解決某一個問題，都可以稱作是演算法，而在這邊我會當作是作用於電腦的。

（設計給電腦執行的解法）

如果不是非電腦的話，泡咖啡的流程也是演算法。

（例：泡咖啡的流程 → 先燒水 → 放咖啡粉 → 注水 → 攪拌 → 完成）

舉一些常見的例子：

  1. Google Map，搜尋一個地址時，要怎麼樣最短的路徑裡面花的時間最短 ——＞ 演算法

  2. youTube，知道怎麼符合喜好，要知道影片有上億個，要能很短的時間內知道某個人該推薦什麼 ——＞ 演算法

  3. facebook/instagram，很常會跳出要不要追蹤好友，但要怎麼要短時間內知道及整理這麼多資料 ——＞ 演算法

為什麼需要 Big O ?

可以很直觀的知道演算法的好壞。

之前學程式的時候，有常識把時間給印出來，看兩段相同邏輯但不同的函式，印出執行時間來看，但每次重整時間其實都不太ㄧ樣，另外也不能保證所有人都是在同一個環境，大家都電腦設備都不一樣。

所以 Big O notation 提供了一種方法，幫助我們在不用實際測試程式的情況下，
就能比較不同演算法在輸入規模變大時的效率差異。

舉例來看時間複雜度：

  • O(1)：無論輸入大小，每次運行所需的步驟數大致固定。

  • O(n)：所需的步驟數，會隨著輸入資料量 n 成比例增加。

  • O(n²)：所需的步驟數，會隨輸入資料量 n 的平方成長。

比如以上三種用時間複雜度的角度來看的話，我自己理解不管今天輸入幾次，O(1)都只要跑一次，所以最好。

而 O(n^2) 每 run n 個就會需要跑 n^2 次，所以這三個之中最差。

所以輸入 n 很小的時候，三者的差異不大，

但 n 很大的時候，三個就會差很多，這也是好的演算法為什麼那麼重要的原因。

了解 Complexlty 的幫助

Complexlty 是複雜度。

有時間複雜度跟空間複雜度，都能以 Big O 來表示。

第一

不用真的去跑才能知道，可以透過複雜度來判斷。

比如說某個演算法在小資料量可能還不錯，但是更多資料的時候還能不能接受，就可以透過複雜度判斷。

第二

能幫助選擇適合的演算法，

同一個問題的解法可能有很多，如果可以知道像是時間複雜度，就能在不同場景選擇最適合的演算法。

第三

溝通上更效率，

像是如果跟同事說：「欸這段程式跑很慢誒」，不精確也很難馬上知道你在說啥，但如果你說「目前是 O(n²)，我們需要想辦法優化到 O(n log n)」，不只清楚的表達了問題，還能讓你看起來很專業。

記錄一下讓我震撼的一段話

看某個 YT 影片在進行軟體工程師面試時，其中有一段是這樣的：

「如果是用 Big O 的話，你會怎麼去 notate 這個 run time」

「如果你有 n number of node，有 n 個 node 的話，它的 run time 是？」

我當下看到他們在討論的時候內心是一片花火的，因為我聽不懂，但我大受震撼，我也想要成爲可以回答這種問題的人。