---
title: 白話演算法！培養程式設計的邏輯思考
tags: Algorithm
description: An illustrated guide for programmers and other curious people
---
# 白話演算法！培養程式設計的邏輯思考
#### 培養程式設計的邏輯思考
---
---
# 章節架構
- 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/
```python=
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)
```python=
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:
```mermaid
flowchart TD
Init[先將收納箱`Main Box`內的所有盒子拿出來排成一堆 `待檢查區`] --> A[只要待檢查區還有盒子, 就拿起一個盒子來檢查]
A --> B[如果裡面還有盒子, 就放到待檢查的那堆盒子中]
A --> C[如果找到鑰匙, 就完成了]
B --> B2[回到盒子堆中拿下一個盒子來檢查]
B2 --> A
```
```python=
# 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:
```mermaid
flowchart TD
Init[逐一拿起盒子檢查] --> A[如果裡面是盒子...]
Init --> B[如果找到鑰匙, 就完成了]
A --> Init
```
```python=
# 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 (遞迴情況): 當函式呼叫自己本身的情況
```python
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
```python
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
```python
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)
Sign in with Wallet
Connect another wallet