CS50 week 3 - Algorithms 筆記

,
👀 6 min read 👀

大家好，我是 Cindy，最近跟同事小夥伴相約一起看 CS50 的課程，CS50 (Introduction to Computer Science）是一堂美國哈佛大學知名的通識課程，完全免費，在 edx 或 youtube 或 CS50-Study-Group github 都可以非常容易地看到。

這系列的文章會是我的個人筆記，歡迎有興趣的人一定要自己去看看 CS50 的課程歐。

今天這篇是 CS50 week 3 筆記，想先看之前筆記的人可以點選下面連結：

Running Times

Big O

用來表示執行所需要最大步驟(n)的最大時間

  • O(n^2)
  • O(n log n)
  • O(n)
  • O(log n)
  • O(1)

Omega

用來表示執行所需要最小步驟(n)的最小時間

  • Ω(n^2)
  • Ω(n log n)
  • Ω(n)
  • Ω(log n)
  • Ω(1)

Theta

當 Big O 和 Omega 相同的時候可以用 Theta 來表示

  • Θ(n^2)
  • Θ(n log n)
  • Θ(n)
  • Θ(log n)
  • Θ(1)

講者用好幾個門表示 Array，當我們想要在這個 Array 中找到一個特定數字，我們從第一個門由左到右一個一個地打開，直到找到想要找的數字為止。

這樣的搜尋方式，如果用 Big O 表示的話就會是 O(n)，n 表示這個 Array 的長度，也就是說我們不幸的在最後一道門打開，才找到想要找的數字。
如果是用 Omega 來表示的話就會是 Ω(1)，因為我們可能很幸運地在第一個門打開，就找到我們要找的數字。

當門後面的數字已經排序好了，我們就可以用 Binary Search，每次切一半搜尋，看打開的數字是比想要找的數字大還小，決定要繼續往左或右的中間搜尋(其實就是 week 0 的時候提到從電話簿中找電話的二分法)，每次都從中間搜尋直到找到想要找的數字為止。

這樣的搜尋方式，如果用 Big O 表示的話就會是 O(log n)，n 表示這個 Array 的長度，log 則是以 2 為底數，如果有 8 個門，每次切一半，最多要切三次才能找到想要找的數字，即 2^3 = 8，也就是 log 8 = 3，故為 log n。
如果是用 Omega 來表示的話就會是 Ω(1)，因為我們可能很幸運地在中間的門打開，就找到我們要找的數字。

Binary Search 比 Linear Search 快得多，當 n 越大的時候會越明顯。

strcmp

在 c 語言中我們不能直接進行 string 的比較(理由會在下堂課程說明)，而在 string.h 中提供給我們進行 string 比較的 function 叫做 strcmp，如果傳入的兩個 string 相同的話會回傳 0，如果第一個 string 比較大的話會回傳正數，如果比較小的話會回傳負數，其中 string 的大小是針對第一個不同的字母經過 ASCII 轉換成數字比較後決定。

structs

透過以下程式碼，我們可以創造自己的 data type：

1
2
3
4
5
6
typedef struct
{
    string name;
    string number;
}
person;

可以用以下方式給值：

1
2
3
4
person people[1];

people[0].name = "Cindy";
people[0].number = "09xx-xxx-xxx";

sorting

Selection Sort

當我們有一串數字需要做排序時，因為電腦只能一個一個的檢查，不像人類可以一眼看出哪個數字最小，所以電腦要從頭到尾一個一個的比較後，挑出最小的數字放到最左邊，並將左邊多出來的數字放到右邊有空缺的位置，接著排除已經排好的數字，繼續從頭到尾掃一次，找出最小的數字，直到排到最後一個數字為止。

假設總共有 n 個數字需要排序，排序的次數如下：
n + (n - 1) + (n - 2) + ... + 1 因為每次都會排好一個數字，所以每次遞減 1
n(n + 1)/2
(n^2+n)/2
n^2/2 + n/2
當 n 越大的時候，具有影響力的會是 n^2，所以用 Big O 表示的話就會是 O(n^2)。
如果是用 Omega 來表示的話就會是 Ω(n^2)，因為就算已經排序好了我們還是得一個個的檢查。
可以用 Θ(n^2) 表示。

Bubble Sort

從左到右每次兩兩比較並排序，如此會像泡泡跑到頂端一樣，最大的數字會最先到頂端(右邊)排好，重複進行兩兩比較，直到最後所有的數字都跑到比較中數字的頂端。

假設總共有 n 個數字需要排序，排序的次數如下：
(n - 1) * (n - 1) 在 n - 1 次(0 到 n)的循環中重複 n - 1 次(從 0 到 n - 2 的兩兩比較)
n^2 - 1n - 1n + 1
n^2 - 2n + 1
當 n 越大的時候，具有影響力的會是 n^2，所以用 Big O 表示的話就會是 O(n^2)。
如果是用 Omega 來表示的話就會是 Ω(n)，因為第一次的兩兩比較發現不需要換任何數字的位置而停止(從 0 到 n - 2 的兩兩比較，實際上是 n - 1，但減 1 可以忽略不計)。

Merge Sort

將數字分成左右各半，分別對左半邊和右半邊進行排序，將排序的兩半合併，合併時每次進行左半和右半的比較，分成一半的時候切到最小單位進行，就可以重複進行合併的比較。

假設總共有 n 個數字需要排序，排序的次數如下：
每次會拿 n 個數字進行合併，因為每次對一半進行排序，所以總共移動 log n 次。
所以用 Big O 表示的話就會是 O(n log n)。
如果是用 Omega 來表示的話就會是 Ω(n log n)，因為就算已經排序好了我們還是得一個個的檢查。
可以用 Θ(n log n) 表示。

雖然這個排序方法更快，但它需要至少另一個 Array 的空間來暫存合併前的數字，即此演算法會需要兩倍的空間。

  • Merge Sort 運用到 Recursion，在函數的定義中使用函數自身的方法(例如：切到最小單位重複進行相同步驟)。

總結

這堂課讓我對於各種演算法有了更深的認識，在寫程式時可以思考使用到邏輯的時間複雜度是什麼，以及考慮到是時間比較便宜還是空間比較便宜，選擇更適合當下情境的演算法。