跟我一起上哈佛神課 CS50-Week 3 Algorithms #2022 #筆記 #中文

課程影片連結：https://video.cs50.io/v_luodP_mfE?screen=J0ND72qsI9U

我們學習新的編程語言或工具的目的是解決問題。

課程大綱 (依影片時間排序)：

課程筆記(依影片時間戳記，可配合影片閱讀)：

0:00:00 Introduction 開場

● 回顧上週，我們學習新的編程語言或工具的目的是解決問題。

我們透過過從輸入創建一些輸出來解決現實中的問題

● 這堂課將專注於介紹解決陣列（arrays）問題的演算法。

0:01:17 Algorithms 演算法

● 想像在記憶體上的每一個儲存空間，是一個置物櫃，裡面依序儲存了不同的字元（character），並組成我們熟知的字串（string）：

圖片下方的數字代表該字元的序號（在陣列中的位置），我們需要打開置物櫃，才知道裡面有什麼

0:05:34 Searching 搜尋

● 在陣列中，我們需要一次打開一個置物櫃，以搜尋需要的資訊。

● 由於陣列是零索引的（zero-indexed），第一個置物櫃索引值為 0。同理如果有 n 個項目，最高索引值將是 n-1。

0:08:17 Big O Notation 大O符號

● 討論搜尋的演算法時，為了比較不同方法的效率，我們需要考慮運行的時間（running time），而電腦科學家傾向用利用大O符號（big O notation）來描述運行的時間，而不是確切的毫秒或是步數。

● 在第 0 週查詢電話簿的時候，我們看過一張圖表，其中包含不同類型的演算法以及其解決問題可能需要的時間：

紅線是線性搜索，一次一頁； 黃線一次搜索兩頁； 綠線是從中間開始，每次把問題一分為二

● 在上面的圖表中，如果我們縮小並更改軸上的單位，會看到紅線和黃線非常接近：

將運行時間改用大O的方式表達

● 我們使用大O符號來描述紅線和黃線，因為它們最終非常相似。 我們將它們描述為具有 “big O of n” 或 “on the order of n” 的運行時間。

● 然而，綠線的形狀明顯地不同，即使它變得非常大。我們將它們描述為具有 “big O of log⁡n” 或 “on the order of logn” 的運行時間。（對數的底數 2 被刪除，因為它是一個常數因子。）

0:12:51 Common Running Times 常見的運行時間

● 大O（big O）用來描述步數的上限，或者在最壞的情況下可能需要多少步：

舉例，常用大O表達的運行時間

● 運行時間為 O(1) 的算法意味著無論問題有多大，都需要固定數量的步驟。

0:13:18 Asymptotic Notation 漸進符號

● 和大O相反，電腦科學家使用大Omega （big Ω）來描述演算法步數的下限，或者在最好的情況下它可能需要多少步：

舉例，常用 Big Omega 表達的運行時間

● 如果上限和下限相同，電腦科學家使用大Theta（big Θ）來描述演算法的運行時間：

舉例，常用 Big Theta表達的運行時間

0:16:50 Searching Lockers 搜尋置物櫃

在影片中，David 邀請學生上台搜尋置物櫃後的隱藏資訊

● 已知有七個鎖著門的置物櫃，後面隱藏著數字；如果我們想尋找數字零，就必須一次打開一扇門。由於我們對門後面的數字一無所知，最簡單的演算法就是從左到右，然而這卻不是最有效率的演算法。

0:20:46 Linear Search 線性搜尋法

● 上述由左至右搜尋的演算法為線性搜尋法。我們可以編寫偽代碼如下：

For each door from left to right
    If number is behind door
        Return true
Return false

● 我們可以重寫我們的偽代碼，使其更接近 C：

For i from 0 to n-1 //will operate n times
    If number behind doors[i]
        Return true
Return false

● 若有 n 個門，我們需要查看 n 個門。 因為我們對 n 扇門中的每一扇門所做的事情，每次都採取固定的步驟，所以這個演算法的大 O 運行時間是 O(n)。

● 此演算法的下限，大Omega ，是 Ω(1)，因為我們可能很幸運並立即找到我們正在尋找的數字，而這需要固定的步驟。

0:29:45 Binary Search 二元搜尋法

● 如果我們知道門後的數字是依序排列的，我們可以從中間開始，更有效地找到我們的值，因為我們知道我們可以向左或向右，每次將問題分成兩半。

● 二元搜尋的偽代碼可編寫如下：

If no doors
    Return false
If number behind middle door
    Return true
Else if number < middle door
    Search left half
Else if number > middle door
    Search right half

● 我們可以重寫我們的偽代碼，使其更接近 C：

If no doors
    Return false
If number behind doors[middle]
    Return true
Else if number < doors[middle]
    Search doors[0] through doors[middle - 1]
Else if number > doors[middle]
    Search doors [middle + 1] through doors[n - 1]

● 如上，我們可以透過一些數學來確定中間門的索引值，然後我們可以將問題劃分為搜尋索引值為 0 到 middle — 1 的門，或者搜索 middle + 1 到 n — 1 的門。

● 二元搜尋法的上限是 O(log⁡n)，因為我們必須不斷將門的數量除以 2，直到沒有更多的門為止。

● 二元搜尋法的下限是 Ω(1)，因為我們正在尋找的數字可能很幸運地在正中間。

0:37:11 Sorting and Searching vs. Just Searching 排序搜尋法 vs. 直接搜尋法

● 儘管二元搜尋法可能比線性搜尋法快得多，它需要先進行排序；如果我們計劃多次搜尋我們的數據，那的確值得花時間先對其進行排序。例如 google 搜尋引擎會將搜尋結果排序以優化搜尋的效率。

● 然而，除了運行程式碼所需的時間之外，我們還要考慮的其他資源包括編寫代碼所需的時間，或者我們的程式碼所需的記憶體容量。所以哪一種搜尋演算法比較好呢？It depends!

0:41:23 Implementing Linear Search 執行線性搜尋

● 將線性搜尋化為程式碼，試著在 numbers 陣列中找到0的位置：

// Implements linear search for numbers
 
#include <cs50.h>
#include <stdio.h>
 
int main(void)
{
    // An array of numbers
    int numbers[] = {4, 6, 8, 2, 7, 5, 0};
 
    // Search for 0
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

● 我們使用{ }花括號初始化一個包含 7 個值的陣列，並且一次檢查一個項目，以查看它們是否等於 0。如果我們找到 0，則返回退出代碼 0（表示成功），否則，在 for 循環結束後，我們返回代碼1（表示失敗）。

0:45:34 String Comparison 字串比較

● 同樣的線性搜尋化也能用於字串的比較嗎？

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"Bill", "Charlie", "Fred", "George", "Ginny", "Percy", "Ron"};

    for (int i = 0; i < 7; i++)
    {
        if (names[i] == "Ron")
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

● 當我們試著編譯時，會獲得以下錯誤代碼：

$ make names
names.c:11:22: error: result of comparison against a string literal is unspecified (use an explicit string comparison function instead) [-Werror,-Wstring-compare]
        if (names[i] == "Ron")
                     ^  ~~~~~
1 error generated.
make: *** [<builtin>: names] Error 1

● 事實證明，我們不能直接在 C 中比較字串，因為它們不是 C 語言中內建的簡單數據類型，而是包含許多字符的陣列。 幸運的是，string程式庫中有函數 strcmp，可以實現字串的比較。

● 如果第一個字串在第二個字串之前，strcmp返回負值；如果兩個字串相同，則返回 0；如果第一個字串在第二個字串之後，則返回正值。

● 我們將條件更改為 if (strcmp(names[i], "Ron") == 0)，這樣我們就可以檢查兩個字串是否實際上相等。此時任何非零值，無論是正的還是負的，都將被認為是true，這與我們想要的相反。此時，我們可以編寫 if (!strcmp(names[i], "Ron"))來反轉值，但這是一種糟糕的設計，因為它沒有明確檢查 0 的值。

0:54:28 Storing Data in Arrays 在陣列中儲存數據

● 在 phonebook0.c 中實現一個電話簿，包含姓名和電話號碼：

// Implements a phone book without structs
 
#include <cs50.h>
#include <stdio.h>
#include <string.h>
 
int main(void)
{
    string names[] = {"Carter", "David"};
    string numbers[] = {"+1-617-495-1000", "+1-949-468-2750"};
 
    for (int i = 0; i < 2; i++)
    {
        if (strcmp(names[i], "David") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

● names 和numbers 是兩個陣列（arrays），其中我們確保每個人的電話號碼和其姓名有相同的索引，則可以藉由搜尋names陣列中的人名，回傳其對應的電話號碼。

● 這個程式是可行卻設計不完善的，因為我們必須分別維護兩個陣列來確保資料的正確，而不是在同一個群組裡面維護。

0:59:36 Structs 結構

● 在 C 中，我們可以定義自己的數據類型（data type）或數據結構（data structure）。 我們可以設計一個 person 類型的陣列people 來包含人們的姓名和電話號碼，即：person people[]; 。

● 使用以下語法創建結構（structs）：

typedef struct
{
    string name;
    string number;
}
person;

● typedef struct告訴編譯器我們正在定義自己的數據結構。 花括號後的 person 則是這個數據結構的名稱。

● 在我們的結構中，我們有兩個字符串，name和number。

● 調整後的電話簿 phonebook1.c 如下：

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[2]; //size = 2

    people[0].name = "Carter";
    people[0].number = "+1-617-495-1000";

    people[1].name = "David";
    people[1].number = "+1-949-468-2750";

    for (int i = 0; i < 2; i++)
    {
        if (strcmp(people[i].name, "David") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

● 點運算符.是為每個 person 結構中的變量設置值的語法。

● 在我們的循環中，我們可以使用 .name 或 .number來訪問結構中的變量，並確保它們來自同一個 person。

● 在電腦科學中，封裝（encapsulation）是指相關數據組合在一起的概念；phonebook1.c 為例，我們將name和number封裝到同一個數據結構中。

1:12:26 Sorting 排序法

● 排序法（Sorting）用來解決將未排序的數字作為輸入，並產生排序數字做為輸出的問題：

舉例輸入 3 1 5 2 4 ，會輸出 1 2 3 4 5

1:13:39 Visualizing Sorts 視覺化排序

David 老師找了八位同學人肉排序給大家看 lol

1:26:22 Selection Sort 選擇排序法

● 選擇排序法的偽代碼：

For i from 0 to n-1  
  Find smallest number between numbers[i] and numbers[n-1]  
  Swap smallest number with numbers[i]

● 總共會排序 n + (n — 1) + (n — 2) + … + 1 = n(n + 1)/2 = (n²+ n)/2 次。

● 由於 n² 是占最大主導的因素，當 n 變得非常大時，我們可以說該算法的運行時間上限為 O(n²)。

● 在最好的情況下，列表已經排序，我們的選擇排序算法仍然會查看所有數字並重複循環，因此它的運行時間下限為 Ω(n²)。

1:34:28 Bubble Sort 泡泡排序法

● 泡泡排序法的偽代碼：

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them

● 總共會排序 (n — 1) × (n — 1) = n² –2n + 1 次。

● 由於 n² 是占最大主導的因素，當 n 變得非常大時，我們可以說該算法的運行時間上限為 O(n²)。

● 如果在演算法中加一點邏輯，我們可以在最佳情況下優化運行時間：

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them
    If no swaps
        Quit

● 在最好的情況下，列表已經排序，因此它的運行時間下限為 Ω(n)。

1:43:03 Comparing Sorts 比較排序法

● 各種排序法的視覺化過程請點我。

1:45:23 Recursion 遞迴

● 遞迴（Recursion）是函數調用自已的能力。 我們還沒有介紹他的程式碼怎麼撰寫，但我們已經在二進位搜尋的偽代碼中看到了這一點：

If no doors
    Return false
If number behind middle door
    Return true
Else if number < middle door
    Search left half
Else if number > middle door
    Search right half

● week0 的電話簿問題，可以將偽代碼修改成遞迴，使得問題的大小變得越來越小：

Pick up phone book
Open to middle of phone book
Look at page
If person is on page
   Call person
Else if person is earlier in book
   Search left half of book
Else if person is later in book
   Search right half of book
Else
   Quit

● week1 的馬力歐磚塊問題，也可以使用遞迴修改如下：

試想第四層磚塊，等於第三層磚塊加一層

#include <cs50.h>
#include <stdio.h>
  
void draw(int n);
  
int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}
  
void draw(int n)
{
    if (n <= 0)
    {
        return;
    }
  
    draw(n - 1);
  
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

$ make recursion
$ ./recursion
Height: 4
#
##
###
####

● 我們重寫draw函數來使用它自己，如果 n 為 0（或以某種方式為負）則停止。

2:00:54 Merge Sort 合併排序法

● 我們可以將recusion 的概念用於排序，使用另一種稱為合併排序法（merge sort）的演算法。 偽代碼可能如下所示：

If only one number
  Quit
Else
    Sort left half of number
    Sort right half of number
    Merge sorted halves

● 舉例而言，若我們分別由左半和右半的數字，且均各自排列好如下：

2 4 5 7 | 0 1 3 6

● 我們將查看每個列表中的第一個數字，並將較小的 0 移動到新列表的開頭。 然後查看列表中的下一個數字：

2 4 5 7 | 0 1 3 6
^         ^

2 4 5 7 |   1 3 6
^           ^
0

● 將下一個最小的數字 1 向下移動，然後查看該列表中的下一個數字：

2 4 5 7 |     3 6
^             ^
0 1

● 這一次，2 是下一個最小的，所以我們將它向下移動，並重複這個過程：

4 5 7 |     3 6
  ^           ^
0 1 2

  4 5 7 |       6
  ^             ^
0 1 2 3

    5 7 |       6
    ^           ^
0 1 2 3 4

      7 |       6
      ^         ^
0 1 2 3 4 5

      7 |
      ^
0 1 2 3 4 5 6

        |
0 1 2 3 4 5 6 7

● 我們現在從一個完全未排序的數字列表開始：

5 2 7 4 1 6 3 0

● 從前半部分開始，這是一個大小為 4 的列表：

5 2 7 4

● 對左半部分進行排序，這是一個大小為 2 的列表：

5 2

● 左半邊是大小 1，右半邊也是大小 1，所以我們可以將兩半合併在一起：

2 5

● 現在對右半部分進行排序：

7 4

● 同樣，我們透過從每個列表中獲取最小元素來將這兩部分合併在一起：

4 7

● 現在我們已經對兩半進行排序，大小均為 2，可以將它們合併在一起：

2 5 | 4 7
^     ^

  5 | 4 7
  ^   ^
2

  5 |   7
  ^     ^
2 4

    |   7
        ^
2 4 5

2 4 5 7

● 右半部分重複此操作，另一個大小為 4 的列表：

1 6 | 0 3
^     ^

1 6 |   3
^       ^
0

  6 |   3
  ^     ^
0 1

  6 |
  ^
0 1 3 

0 1 3 6

● 現在，我們有兩個排序的一半，2 4 5 7 和 0 1 3 6，可以合併在一起。

● 每次我們合併兩半時，我們只需要查看每個數字一次。 我們將 8 個數字的列表除以三倍，即 log⁡ n 倍。 我們需要更多的記憶體空間來合併我們的新列表，但合併排序法的運行時間上限僅為 O(n log⁡ n)， 小於 O(n²)。

● 合併排序法的運行時間下限仍然是 Ω(n log⁡ n)，因為即使列表已排序，我們也必須完成所有工作。

2:15:16 Sort Race 排序法比賽

具有大量輸入的排序演算法同時運行，各自的效果如何呢？請看影片。

以上就是本週的課程! 如果你喜歡我的筆記 歡迎收藏或是為我鼓掌呦!
see you !