【CS50 學習筆記】week3 — 了解Linear Search 、Binary Search、Bubble Sort、Selection Sort 和Merge Sort
搜尋法
在 week 0 週的筆記中演算法的段落有提到以電話簿找尋人名可以有三種方法，第一種是一頁一頁翻，直到找到為止，第二種是兩頁兩頁翻，直到找到為止，但不可靠，這兩種是屬於線性搜尋（Linear Search），第三種是二分搜尋法（Binary Search），透過每次搜尋就捨棄一半數列的方式來找，以下的連結是他們將這兩種搜尋法以視覺化的方式來呈現。
Running Time
演算法該如何判別好壞，有空間（Space Complexity）和時間（Time Complexity）的方式能做比較，這篇只先討論時間，時間的話通常會以 big O 的方式來表達這個演算法搜尋的效率為何：
- （O）Big-O：演算法時間函式的上限 (Upper bound) 即「最差」情況下的執行次數
例如 Linear search 會是以 O(n) 表示，代表隨著 n 變大，其「最差」的搜尋情況就是 n，在電話簿的例子中若電話簿有 300 頁，要找尋 David 這個人，但好巧不巧這個名字就在最後一頁，因此最佳最差的情況就是 300 頁都要翻過。但到了 Binary Search 就是以 O(log n) 表示，以 2 為底的 log，隨著 n 變大，其「最差」的搜尋情況一樣會增加，但並不會增加太多，整條線呈現遞減的。
常見的時間複雜度為為以下（花費時間由大至小）：
- O(n²) ：次方時間（Quadratic Time）
- O(n log n)：線性乘對數時間（Quasilinear Time）
- O(n)：線性時間（Linear Time）
- O(log n)：對數時間（Logarithmic Time）
- O(1)：常數時間（Constant Time）
另外有兩個符號會用來衡量演算法的效率：
- Ω (Omega)：演算法時間函式的下限(Lower bound)，如 Linear search 和Binary Search 都會表示成 Ω(1)，亦即最好的情況下我只要一步就能找到
- θ (Theta)：當演算法時間函式的上限與下限相同就會表示成 theta
Linear Search
CS50 課堂中給了以下的 code 來呈現 linear Search，給定一個裡面為 number 的 array，並詢問使用者要搜尋的 number 為何，將 array 做迴圈，由左至右去比對使用者想找的 number，若有找到則印出 Found 並 return 0，無則印出 Not found 並 return 1。
#include <cs50.h>
#include <stdio.h>
int main(void)
{
// An array of integers
int numbers[] = {20, 500, 10, 5, 100, 1, 50};
// Search for number
int n = get_int("Number: ");
for (int i = 0; i < 7; i++)
{
if (numbers[i] == n)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;
}接著若改變 array 裡面的變數型態，從 number 變成 string，如以下，此時需要注意的是比對時就不能用 ==，而是要用 string.h library 的 strcmp
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
// An array of strings
string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"};
// Search for string
string s = get_string("String: ");
for (int i = 0; i < 6; i++)
{
if (strcmp(strings[i], s) == 0)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;
}再來又舉了一個例子是想用人名去印出相對應的電話，如以下設計了兩個 array，一個為人名的 array，一個為電話的，Carter 去對應 +1–617 開頭的電話，David 去對應 +1–949 開頭的電話，但這樣的設計並不是很好，因為若增減人名和電話都必須確保他們的 index 值是對應的，因此是否我們能制定一種相關聯的資料型態來儲存，那就能確保在增減資料時不會出現關聯錯誤的情況。
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
// Arrays of strings
string names[] = {"Carter", "David"};
string numbers[] = {"+1-617-495-1000", "+1-949-468-2750"};
// Search for name
string name = get_string("Name: ");
for (int i = 0; i < 2; i++)
{
if (strcmp(names[i], name) == 0)
{
printf("Found %s\n", numbers[i]);
return 0;
}
}
printf("Not found\n");
return 1;
}Data Structures
C 這個語言則允許我們透過 struct 去創造自己的資料型態，以下命名這樣的型態為 person ，接著就能命名一個名為 people 的 array，裡面的資料型態則是自創的 person ，然後將想要塞入的資料塞入，此時每個人都會有一個專屬的 index，裏面就會有對應的人名和電話。
#include <cs50.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
string name;
string number;
}
person;
int main(void)
{
person people[2];
people[0].name = "Carter";
people[0].number = "+1-617-495-1000";
people[1].name = "David";
people[1].number = "+1-949-468-2750";
// Search for name
string name = get_string("Name: ");
for (int i = 0; i < 2; i++)
{
if (strcmp(people[i].name, name) == 0)
{
printf("Found %s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}Sorting
排序的目標在於將一串大小排列不一的數列排成由小至大的數列，接著就能透過搜尋法如 binary search 去找尋資料，因此這個排序的前置作業能減輕電腦搜尋的負擔，不過排序法有很多種，以下簡介一些基本的排序法，可以搭配以下視覺化的工具來理解。
- 選擇排序
pseudocode 如下，主要是先預設第一個值為最小值，接著往後一個個找，若找的值更小，就將他們換位，這麼一來會把最小值從左至右排出。
For i from 0 to n–1
Find smallest number between numbers[i] and numbers[n-1]
Swap smallest number with numbers[i]如以下的數列，預設 5 為最小值，往後找，2 比 5 小則最小值換成 2 ，2 比 7 小略過，2 比 4 小略過，2 比 1 大則最小值換成 1，1 比 6 小略過，1 比 3 小略過，1 比 0 大則最小值換成 0，找完一輪後這輪最小值為 0，因此把 5 和 0 換位，進到下一輪，這時因為 0 已經排好，所以預設 2 為最小值，然後也是往後比較，直到所有數值都被排好。
5 2 7 4 1 6 3 0
=> 0 | 2 7 4 1 6 3 5
=> 0 1 | 7 4 2 6 3 5
=> 0 1 2 | 4 7 6 3 5
=> 0 1 2 3 | 7 6 4 5
=> 0 1 2 3 4 | 6 7 5
=> 0 1 2 3 4 5 | 7 6
=> 0 1 2 3 4 5 6 | 7
=> 0 1 2 3 4 5 6 7時間複雜度：處理的步驟為（n-1)+(n-2)+…3+2+1 = n²/2–n/2，從式子來看 n² 為最大的影響指標，因此此演算法為 O(n²)，但今天若數列已經按照小到大排好，仍還是要執行一樣的步數才能知道，所以最好的情況下為 Ω(n²) ，因為最好和最壞的步數一樣，可以表達成 θ(n²)。
2. 泡沫排序法
pseudocode 如下，和選擇排序法不同的是他是先預設第一個值為最大值，接著和他下一個值比，第一個若比較大則換位，若比較小則讓下一個值作為最大值，所以一輪過去就會產生該輪的最大值並排在最右側。
Repeat n-1 times
For i from 0 to n–2
If numbers[i] and numbers[i+1] out of order
Swap them如以下的數列，5 預設為該輪最大值，接著和 2 比較，5 比較大則換位，5 比 7 小則 7 為最大值，7 和 4 比，7 比較大則換位，7 和 1 比換位，7 和 6 比換位，7 和 3 比換位，7 和 0 比換位，這輪就排好 7 了，再來第二輪預設 2 為最大值，也是照剛剛的規則排下去，直到所有數值都排好。
5 2 7 4 1 6 3 0
^ ^
2 5 7 4 1 6 3 0
^ ^
2 5 7 4 1 6 3 0
^ ^
2 5 4 7 1 6 3 0
^ ^
2 5 4 1 7 6 3 0
^ ^
2 5 4 1 6 7 3 0
^ ^
2 5 4 1 6 3 7 0
^ ^
2 5 4 1 6 3 0 7時間複雜度：處理的步驟為（n-1)+(n-2)+…3+2+1 = n²/2–n/2，從式子來看 n² 為最大的影響指標，因此此演算法為 O(n²)，但今天若數列已經按照小到大排好，在第一輪時若所有的數值都沒換位，即代表已經是排好的數列，因此，所以僅需花費 n-1 步，最好的情況會被視為 Ω(n) 。
Recursion
「遞迴」是在一個函式內再呼叫自己的寫法，在第一週有提到要透過程式印出瑪利歐遊戲的方塊城牆如以下：
#
##
###
####一開始或許會這樣寫：
int main(void)
{
int height = 4;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < i + 1; j++)
{
printf("#");
}
printf("\n");
}
}但到了遞迴的寫法就會變以下，在 draw 這個函式內會看到再呼叫自己，但傳入的參數是不同的，不過也還是需要在呼叫前設定停止點，否則會進入無限迴圈。
void draw(int n);
int main(void)
{
int height = 4;
draw(height);
}
void draw(int n)
{
if (n < 1) return;
draw(n - 1);
for (int i = 0; i < n; i++)
{
printf("#");
}
printf("\n");
}
Merge Sort
現在可以藉由遞迴這個觀念來寫更有效率的排序法，稱作合併排序法，pseudo code 如下，藉由不斷拆解數列並合併的方式來整合數列，也就是divide and conquer。
If only one number
Quit
Else
Sort left half of number
Sort right half of number
Merge sorted halves直接寫個例子如下，在拿到數列後要先判斷是否這個數列只有一個數字，若否則將數列拆成左半邊和右半邊，先看左半邊， 7 和 2，再拆左半和右半，因為 7 和 2 都只有一個數字，因此進入的合併的環節，2 和 7 比 2 比較小，因此他們會合併為 2 7，換右半邊 5 4 排，一樣都只有一個數字，因此會合併為 4 5，最後兩邊要合併成最終數列，2 和 4 比 2 小，7 和 4 比 4 小，7 和 5 比 5 小，最後就變成 2 4 5 7。
7 2 5 4
拆解
=> 7 2 ｜ 5 4
=> 7 ｜ 2 ｜ 5 ｜ 4
合併
=> 2 7 ｜ 4 5
=> 2 4 5 7時間複雜度：為 θ(n log n)，最差和最好都一樣，拆分會是 n-1 步，合併會是 n * log n ，每一輪合併每個數都會拿起來比較所以是 O(n)，總共會有 log n 輪，因為每一次都將組數砍半，加起來是 n-1 + n * log n ，取最高項係數就為 n * log n， 至於更為圖像化的講解複雜度可以參考這篇《初學者學演算法｜排序法進階：合併排序法》。
總結：
過了一個月才有這篇，主要是還要寫作業和處理公司的事情，加上過年有幾天都在追劇 😗，這篇知道了三種排序法和遞迴，當然還有其他的排序法如插入排序和快速排序等等沒提，但這週就先這樣，CS50 也提供了以下影片來比較各種排序法他們排列的速度，還滿清楚他們完成的時間先後：
希望下一篇可以兩個禮拜內生出來 ( ´•̥̥̥ω•̥̥̥` )
