白話演算法！培養程式設計的邏輯思考

培養程式設計的邏輯思考

---

---

章節架構

• Ch1 - 二元搜尋法(Binary Search)與演算法執行時間
• Ch2 - 選擇排序法(Selection Sort)
• Ch3 - 遞迴(Recursion)
• Ch4 - Divide-and-Conquer與快速排序法(Quicksort)
• Ch5 - 雜湊表(Hash table)
• Ch6 - 廣度優先搜尋(Breadth-First Search)
• Ch7 - 戴克斯特拉(Dijkstra)演算法
• Ch8 - 貪婪演算法(Greedy Alogrithm)
• Ch9 - 動態規劃演算法(Dynamic Programming Alogrithm)
• Ch10 - K-最近鄰演算法(K-Nearest Neighbors Alogrithm)
• Ch11 - 進階之路：推薦十種演算法

---

Ch1 二元搜尋法(Binary Search)與演算法執行時間

1-1 二元搜尋法(Binary Search)

Example: 終極密碼(猜數字)

有玩過猜數字嗎？如果想要快速減少數字的範圍，以最少的次數猜到數字，你會怎麼做？

二元搜尋法(Binary Search)

二元搜尋法(Binary Search)是一種演算法，但是被搜尋的清單內容必須先經過排序。如果你要找的元素在清單內，二元搜尋就會回傳該元素的位置編號；若要找的元素不在清單內則會回傳null。

如果我享受遊戲的樂趣，喜歡從1開始慢慢猜，猜到數字99，那它有名字嗎？
Ans: 簡易搜尋法

Example2: 查單字

如果字典裡有24萬個字，在最差的情況下，簡易搜尋法和二元搜尋法分別需要多少步驟呢？

• 簡易搜尋：24w 次
• 二元搜尋：18 次

24w -> 12w -> 6w -> 3w -> 15k -> 7.5k -> 3750 -> 1875 -> 938 -> 469 -> 235 -> 118 -> 59 -> 30 -> 15 -> 8 -> 4 -> 2 -> 1

對數(logarithm)與指數(mathematical power, power)

log2 240000 = 17.872674880270605 -> 18

Binary Search in Python:
https://replit.com/@YuTingHuang2/algorithms
https://www.geeksforgeeks.org/python-program-for-binary-search/

def binary_search(list, item):
  low = 0
  high = len(list) - 1

  while low <= high:
    mid = (low + high) // 2 # = (low + height)/2 答案無條件捨去
    mid_num = list[mid]
    if mid_num == item:
      return mid
    elif mid_num > item:
      high = mid - 1
    else:
      low = mid + 1
  return None # null

#my_list= [0, 1, 2, 3, 4, 5, 6, 7]
my_list = [1, 3, 6, 7, 9, 13, 17, 18]
print(binary_search(my_list, 9))

my_list = [1, 3, 6, 7, 9, 13, 17, 18]
print(binary_search(my_list, 8))

演算法的執行時間
簡易搜尋法：線性時間(Linear time)
二元搜尋法：對數時間(Logarithmic time, 簡稱log time)

1-2 Big O notation (大O符號)

評估演算法效益的方法，通常是用來表示演算法的執行速度，代表的時最差的情況的執行時間

請注意！演算法的執行時間不會隨著元素的增加而等比增加

	簡易搜尋法	二元搜尋法
100個元素	100毫秒	7毫秒
10,000個元素	10秒	14毫秒
1,000,000,000個元素	11天	30毫秒

Big O notation，用運算次數來計算執行時間

• 簡易搜尋法（每個元素都要執行一次）： O(n)
• 二元搜尋法： O(log n)

常見的Big O執行時間

• O(log n): 對數時間. ex: 二元搜尋法
• O(n): 線性時間. ex: 簡易搜尋法
• O(n*log n): ex: 快速排序法
• O(n^2): ex: 慢速排序法和選擇排序法
• O(n!): 非常慢的演算法 ex:旅行推銷員

Ch2 選擇排序法(Selection Sort)

2-1 記憶體是如何運作的呢？

想像一下，我們旅行會想要寄放行李在置物櫃，每個格子都只能放一件物品，如果要寄放兩件物品，就需要兩個格子。

基本上，電腦的記憶體也是這樣運作的。電腦就像是一個巨大的櫃子，每個抽屜都有自己的位置(address)。

每次要將元素存入記憶體時，都必須要請電腦空出一些空間，而電腦給你的是一個可以儲存該元素的位置。如果要儲存多個元素時，可以使用 陣列(array) 或 鏈結串列(linked list)的方法。

2-2 陣列(array) 與 鏈結串列(linked list)

如果要開發一個管理代辦事項的程式，就得將多個代辦事項存入記憶體。那此時該選陣列還是鏈結串列呢？

陣列(array)

所有代辦事項都連續(緊鄰著)存入記憶體。比如說自由入座的電影院位置，當朋友三人已入座，此時有第四個朋友臨時加入，我們就必須移動到有連續四個空位的位置，如果又有人要臨時加加，就得再次移動了。

缺點：

• 浪費空間
• 超出預期得再次移動

鏈結串列(linked list)

有點像尋寶的概念。你要先到第一個位址，上面寫著「去位址123可以找到下個元素」。不用堅持緊鄰相依，也不用大家一起搬來搬去，只要在記憶體內隨便找個空位把位址存到上一個元素就好了。

如果在電影院大爆滿的情況下，你們6個人要找位置，鏈結串列就會說：「我們分頭找座位看電影吧！」

陣列與鏈結串列的優缺點

• 陣列：如果需要隨機讀取，陣列非常適合，因為可以瞬間讀取陣列內的任一元素
• 鏈結串列：如果要逐一讀取元素，那鏈結串列非常適合

陣列的「索引」(index)

陣列內每個位置都有編號，這個編號（位置）叫做索引(index)。編號是從0開始，本書會用索引取代位置

	array	linked list
讀取(read)	O(1)	O(n)
插入(insert)	O(n)	O(1)
刪除(delete)	O(n)	O(1)

資料的存取方式

• 循序存取(Sequential access): 從第一個元素開始依序逐一存取
• 隨機存取(Random access): 可以依資料索引位置直接存取內容

2-3 選擇排序法 (Selection sort)

假如電腦裡有一份紀錄每位歌手播放次數的記錄表，若想依播放次數的高低來排序，該怎麼做比較好？

• Step 1. 找出播放次數最多的
• Step 2. 找出播放次數第二多的
• …不斷重複上述步驟，就能得到一個排序好的表格

時間複雜度：O(n x n) || O(n^2)

def find_smallest_index(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
        smallest_index = i
        smallest = arr[i]
    return smallest_index

def selection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest_index(arr)
        new_arr.append(arr.pop(smallest))
        
    return new_arr

print(selection_sort([5, 3, 8, 4, 13])) # [3, 4, 5, 8, 13]

Camparsion between Array and Linked List

–-	array	linked list
元素的存放	一個接一個連續排列	分散在各處
存取方式	隨機存取	循序存取
插入操作	需要搬移插入點之後的所有元素，若沒有空間會發生錯誤。執行時間: O(n)	只需更改元素的指向位置。執行時間：O(1)
刪除操作	刪除元素後，後續的元素要往前搬動。執行時間： O(n)	只需更改元素的指向位置。執行時間： O(1)

Ch3 遞迴 (Recursion)

認識遞迴 (Recursion)

想像有一個收納箱，裡面有很多大大小小的盒子，盒子的裡面還有多個小盒子，你要找一個鑰匙，就在其中一個盒子裡面

方法 1:

# Pseudo code - Iteration
def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                print("find the key!")

方法 2:

# Pseudo code - Recursion
def look_for_key(box):
    for item in box:
        if item.is_a_box():
        look_for_key(item)
        
    elif item.is_a_key():
        print('find the key!')

迴圈可能會提升程式的效能，但遞迴可能會提升程式設計師的效益。請依不同情況做選擇！

Leigh Caldwell

選多重要的以算法都使用Recusrion，所以理解遞迴的概念非常重要！

遞迴的Base Case 與 Recursive Case

沒有加入停止遞迴的機制，你的遞迴就會是一個無窮迴圈

何時該停止遞迴？
遞迴的組合：

• Base Case (基本情況): 當函式不再呼叫自己時間的情況
• Recursive Case (遞迴情況): 當函式呼叫自己本身的情況

def countdown(i):
    print(i)
    if i <= i: # Base Case
        return
    else: # Recursive Case
        countdown(i - 1)

3-3 堆疊(Stack) 在函式呼叫與遞迴的運用

堆疊(Stack)
一種資料結構，函式呼叫時會用到堆疊技術。堆疊是一種有順序性的資料結構，「最晚放入stack」的資料會「最先被取出」(LIFO, Last-In-First-Out)；而「最早放入堆疊」的資料會「最後被取出」(FILO, First-In-Last-Out)

呼叫堆疊 Call Stack

def greet2(name):
    print("how are tou, ", name, "?")
    
def bye():
    print("ok, bye!")
    
def greet(name):
    print("hello, ", name, "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()
    
greet("Yvonne")

# output:
# hello, Yvonne!
# how are you, Yvonne?
# getting ready to say bye...
# ok bye!

Call Stack and Recursion

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)
    
print(factorial(6))

回到一開始的收納箱裡面一堆盒子的example (literation & Recursion)，使用Recursion會透過stack的方式執行function，所以不需要自己紀錄哪些盒子尚未檢查，因為堆疊已經幫你記錄好了

Stack的缺點：

• 存放的資料很佔記憶體空間

處理過多Stack的方式：

• 將程式碼以迴圈的方式改寫
• 使用尾端遞迴(tail recursion)。不過，這是比較進階的遞迴主題，不是在本書探討的範圍內，而且並非所有程式語言都支持尾端遞迴

Question: 假設不小心寫了一個無限循環（沒有停止點）的遞迴函式，電腦會對堆疊內的每個函式呼叫分配記憶體。如果遞迴函式不斷執行，最後會變成怎樣？
Answer: 堆疊會無限增長，當空間用完時，程式就會因為堆疊溢位(stack overflow)而停止執行

4 Divide-and-Conquer & Quicksort

4-1 Divide-and-Conquer

Divide-and-Conquer(D&C) 的概念是：將一個複雜的問題拆解成多個子問題，再用遞迴(Recursion) 求出子問題的答案，最後將這些子問題的答案合併在一起，就可以得到原本複雜問題的答案了！

許多演算法都用到D&C的技巧，例如：

• 二分搜尋法(Binary Search)
• 合併搜尋法(Mergesort)
• 快速排序法(Quicksort)