演算法入門(一) 演算法與大 O 符號

演算法

演算法三步驟，它是明確的、有限的且有效率的

1. 輸入
2. 計算步驟
3. 輸出

工欲善其事，必先利其器

假設現在目標是砍倒一棵樹，且不限時間，使用斧頭會需要很多時間也浪費力氣，使用電鋸省力也省時，換成步驟來看的話，斧頭需要很多砍很多下才會倒，且需要的時間非常多，換成電鋸後，省時省力。

再假設你買了一部90萬的車輛，朋友問你這部車買了多少? 你只能打字回答，這時你會怎麼回覆呢? 9000百元? 900千元? 或者90萬元? 顯然是90萬元最符合答案也能最快回答。

如何描述程式中時間與空間的關係呢?

我們會以數學符號之漸進符號 $O$，其表示為函數增長關係。

• 漸進符號 $O$
  • bigO，通常會寫成 $O()$
• 時間複雜度
  • 隨著輸入值成長之執行步驟
• 空間複雜度
  • 隨著輸入值成長之記憶體暫用空間

而通常我們為了簡化表達方式，會取其極限值，以下為一些例子 :

• 常數 $\rightarrow$ 1
• $n、2n、3n \rightarrow n$
• $n^2+2n \rightarrow n^2$
• 以此類推

執行複雜度表示方式

來看以下的例子，小杰被師父指派去賣漢堡，每個漢堡50元 :

• 範例一

  const sell = (n) => {
    let total = n*50
    return total
  }

  此函式一共執行 2個步驟，也就是說輸入無窮大時，也只會執行 2個步驟，那麼它的時間複雜度則為 $O(1)$，空間複雜度為 $O(1)$，因為只使用了 total這個變數。

• 範例二

  const sell = (n) => {
    let total = n*50
    for (let i = 0; i < n; i++){
      console.log(`小杰累計賣出${i}個漢堡~`)
    }
    return total
  }
  sell(100)

  for迴圈執行了 n次再加上前後兩個步驟共 n+2次，以時間複雜度來表示則為 $O(n)$，空間複雜度為 $O(1)$，使用了 total與 i兩個變數

參考來源

1. Long - 用JavaScript學習資料結構與演算法
2. 胡程維 - 初學者學演算法