iT邦幫忙

2021 iThome 鐵人賽

DAY 2
0
自我挑戰組

【用 JS 學演算法】前端工程師學徒系列 第 2

【Day 02】認識演算法 Algorithm ( 使用 JavaScript )

一、什麼是演算法 ( Algorithm ) ?

演算法是一組 step by step 用來解決問題、完成任務的指令,它的定義:

  • 在有限時間內
  • 在有限步驟內
  • 一步一步解決一個問題的方法

輸入 + 演算法 = 輸出

二、演算法的目的

在程式中,可以使用迴圈、if else 等邏輯,來定義程式的運作與流程控制,例如:

  • 循序 / 非同步
  • 分支
  • 重複

而演算法可以簡單地想像為複雜版的流程控制,用更複雜的邏輯,優化迭代出更有效率的方法,來解決問題。

演算法的目的是提升時間複雜度,更有效率地控制程式流程

三、演算法與運算思維

而在面對問題時,先別急著馬上寫程式,我們可以透過運算思維,先思考要如何拆解問題、整理自己的想法,再來轉換成程式碼表達。

運算思維 ( Computational Thinking ) 的步驟

  1. 拆解:將問題拆解成較好處理的小問題 ( ex. Divide-and-Conquer )
  2. 規律辨識:檢視小問題,觀察是否有規律或趨勢存在
  3. 抽象化:找出通則 ( 用數學符號表示 )
  4. 演算法:設計、歸納出步驟來解決問題

四、透過猜數字遊戲來了解演算法

接下來透過終極密碼猜數字的遊戲,來稍微感受一下演算法。

我們有 1 到 100 的數字 ( 有順序性 ),妳要如何用最快的方法猜到我心中設定的數字呢 ?

方法一:
按照 1、2、3、4 … 依序往下猜,每猜一次就剔除一個數字。這樣地簡易搜尋,其實就算一個演算法。
讓我們試著用正式一點的「虛擬碼」( Pseudocode ) 來表達:

set item be 90

for i (from 1 to 100) do
  if guess = item then
    print("Correct")
  end if
end for

但是,如果我設定的數字是 90,方法一就得猜 90 次才猜的到。最壞的情況要 100 次 !
那有沒有更快速的方法呢 ?

方法二:
從中間的 50 開始應該是比較好的辦法,雖然比較低,但是馬上剔除一半的數字。
接下來從 75 開始猜 ( 50 到 100 的中位數 ),還是太低,但我們又去除掉了一半的數字 ( 50 到 75 )
就這樣從中間的位置開始猜,每次可以剔除一半的數字,最多 7 次就可以猜到了吧 !

arr is an array from 1 to 100
let low be 0
let high be arr.length-1

set item be 90

while low < high do
  mid = (low+high)/2
  guess = arr[mid]
  if guess = item then
    return mid
  end if
  if guess < item then
    low = mid + 1
  else
    high = mid - 1
  end if
end while

方法二這樣類似的搜尋方式,就是使用二進位搜尋 ( Binary Search ) 演算法來解決問題。

如果今天數字很大很大用 n 表示的話,最壞的情況下,方法一需要 n 個步驟才能完成,但方法二只需要 log n 個步驟就好。

原文連結:認識演算法 Algorithm ( 使用 JavaScript ) - Ted's Point 泰德觀點


上一篇
【Day 01】認識資料結構 Data Structure ( 使用 JavaScript )
下一篇
【Day 03】如何評估演算法的效率? Big O 與時間複雜度
系列文
【用 JS 學演算法】前端工程師學徒9

尚未有邦友留言

立即登入留言