4.1. 第 3 周：算法¶
4.1.1. 欢迎！¶
在第零周，我们介绍了 算法 的概念：一个可能接受输入并生成输出的黑盒。
本周，我们将通过伪代码进一步扩展对算法的理解，并最终深入到代码本身。
此外，我们将考虑这些算法的效率。事实上，我们将基于上周讨论的一些概念来构建算法，从而深化我们的理解。
展示各种运行时间的图表
考虑下图：
算法可能很慢，具有较高的时间和处理成本；也可能很快，具有较低的处理和时间成本。
随着我们进入本周，你应该考虑算法解决问题的方式如何决定解决问题所需的时间！算法可以被设计得越来越高效，直至达到极限。
今天，我们将专注于算法的设计以及如何衡量其效率。
4.1.2. 线性查找¶
回想一下，上周你接触到了 数组 的概念，即连续的内存块：彼此并排排列。
你可以比喻性地将数组想象为如下所示的一排七个红色储物柜：
七个红色储物柜并排排列
[0] [1] [2] [3] [4] [5] [6]
最左侧的位置称为 位置 0 或 数组的起始位置 。最右侧的位置是 位置 6 或 数组的末尾位置 。
我们可以设想有一个基本问题：“数字
50是否在数组中？”计算机必须查看每个储物柜才能确定数字50是否在其中。我们将这种查找数字、字符、字符串或其他项的过程称为 查找 。我们可以将数组交给一个算法，该算法会遍历我们的储物柜，检查数字
50是否在某扇门后，并返回值true或false。我们可以设想为执行此任务而向算法提供的各种指令如下：
For each door from left to right If 50 is behind door Return true Return false请注意，上述指令被称为 伪代码 ：一种人类可读的指令版本，我们可以将其提供给计算机。
计算机科学家可以将该伪代码翻译如下：
For i from 0 to n-1 If 50 is behind doors[i] Return true Return false请注意，上述内容仍然不是代码，但它非常接近最终代码可能的样子。
4.1.3. 二分查找¶
二分查找 是另一种可用于我们寻找
50任务的 查找算法 。假设储物柜中的值已按从小到大排列，二分查找的伪代码如下所示：
If no doors left Return false If 50 is behind middle door Return true Else if 50 < middle door Search left half Else if 50 > middle door Search right half使用 code 的术语，我们可以进一步修改我们的算法，如下所示：
If no doors left Return false If 50 is behind doors[middle] Return true Else if 50 < doors[middle] Search doors[0] through doors[middle - 1] Else if 50 > doors[middle] Search doors[middle + 1] through doors[n - 1]请注意，通过查看这段代码的近似表示，你几乎可以想象它在实际代码中的样子。
4.1.4. 运行时间¶
你可以考虑算法解决问题所需的时间。
展示大 O 记号下各种运行时间的图表
计算机科学家讨论算法效率时，并不极度关注其数学上的精确效率，而是用 阶 来描述各种运行时间。
在上图中，第一个算法是 \(O(n)\) 或 n 的阶 。第二个也是 \(O(n)\)，因为在大 O 表示法中常数被忽略。第三个是 \(O(\log n)\)。
正是曲线的形状体现了算法的效率。我们可能会见到的一些常见运行时间包括：
\(O(n^2)\)
\(O(n \log n)\)
\(O(n)\)
\(O(\log n)\)
\(O(1)\)
在上述运行时间中，\(O(n^2)\) 被认为是最慢的运行时间。\(O(1)\) 是最快的。
线性查找的阶为 \(O(n)\)，因为在最坏情况下它可能需要 n 步才能完成。
二分查找的阶为 \(O(\log n)\)，因为即使在最坏情况下，它所需的步骤也会越来越少。
程序员既关注最坏情况（即 上界 ），也关注最好情况（即 下界 ）。
符号 \(\Omega\) 用于表示算法的最好情况，例如 \(\Omega(\log n)\)。
符号 \(\Theta\) 用于表示上界与下界相同的情况：即最好情况与最坏情况的运行时间相同。
渐近记号 是衡量算法在输入规模不断增大时表现如何的指标。
随着你在计算机科学领域知识的不断深化，你将在未来的课程中更深入地探讨这些主题。
4.1.5. 查找¶
你可以通过在终端窗口中输入
code search.c并编写如下代码来实现线性查找：// Implements linear search for integers #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; }
请注意，以
int numbers[]开头的行允许我们在创建数组时定义其每个元素的值。接着，在for循环中，我们实现了线性查找。return 0用于表示成功并退出程序。return 1用于以错误（失败）状态退出程序。我们现在已经用 C 语言自己实现了线性查找！
如果我们要在数组中查找一个字符串该怎么办？按如下方式修改你的代码：
// Implements linear search for strings #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; }
注意，我们无法像本程序的前一次迭代那样使用
==。相反，我们使用来自string.h库的strcmp。如果字符串相同，strcmp将返回0。另外请注意，6的数组长度是硬编码的，这不是良好的编程实践。确实，运行这段 code search.c 允许我们遍历这个字符串数组，以查看某个特定字符串是否在其中。然而，如果你遇到 segmentation fault ，即你的程序访问了本不应访问的内存部分，请务必确保你上面标注的是
i < 6而不是i < 7。你可以在 CS50 Manual Pages 了解更多关于
strcmp的信息。
4.1.6. 电话簿.c¶
我们可以将数字和字符串的这些概念结合到一个程序中。在终端窗口中输入
code phonebook.c，并编写如下代码：// Implements a phone book without structs #include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { // Arrays of strings string names[] = {"Kelly", "David", "John"}; string numbers[] = {"+1-617-495-1000", "+1-617-495-1000", "+1-949-468-2750"}; // Search for name string name = get_string("Name: "); for (int i = 0; i < 3; i++) { if (strcmp(names[i], name) == 0) { printf("Found %s\n", numbers[i]); return 0; } } printf("Not found\n"); return 1; }
注意 Kelly 的号码以
+1-617开头，David 的电话号码以+1-617开头，而 John 的号码以+1-949开头。因此，names[0]是 Kelly，numbers[0]是 Kelly 的号码。这段代码将允许我们在电话簿中查找某人的特定号码。虽然此代码可以工作，但存在许多低效之处。事实上，姓名和电话号码可能无法相互对应。如果我们能够创建自己的数据类型，将人员与其电话号码关联起来，那岂不是更好？
4.1.7. 结构体¶
事实证明，C 允许我们通过
struct创建自己的数据类型。创建一个名为
person的自定义数据类型，其中包含一个name和一个number，难道没有用吗？请看以下内容：typedef struct { string name; string number; } person;
请注意，这表示我们自己的数据类型
person，它包含一个名为name的字符串和另一个名为number的字符串。我们可以通过如下方式修改电话簿程序，从而改进之前的代码：
// Implements a phone book with structs #include <cs50.h> #include <stdio.h> #include <string.h> typedef struct { string name; string number; } person; int main(void) { person people[3]; people[0].name = "Kelly"; people[0].number = "+1-617-495-1000"; people[1].name = "David"; people[1].number = "+1-617-495-1000"; people[2].name = "John"; people[2].number = "+1-949-468-2750"; // Search for name string name = get_string("Name: "); for (int i = 0; i < 3; i++) { if (strcmp(people[i].name, name) == 0) { printf("Found %s\n", people[i].number); return 0; } } printf("Not found\n"); return 1; }
请注意，代码以
typedef struct开始，其中定义了一个名为person的新数据类型。在person内部，有一个名为name的字符串和一个名为number的string。在main函数中，我们首先创建一个名为people的数组，其类型为person，大小为 3. 然后，我们更新people数组中三个人的姓名和电话号码。最重要的是，请注意 点表示法 （例如people[0].name）如何让我们访问位于第 0 个位置的person并为该个体分配一个姓名。
4.1.8. 排序与选择排序¶
排序 是将一个无序的值列表转换为有序列表的操作。
当列表有序时，在该列表中执行查找操作对计算机的负担要小得多。回想一下，我们可以在有序列表上使用二分查找，但在无序列表上则不行。
事实证明，存在许多不同类型的排序算法。
选择排序 就是其中一种排序算法。
我们可以将数组表示如下：
七个红色储物柜并排排列，最后一个标记为 n-1
[0] [1] [2] [...] [n-3] [n-2] [n-1]
选择排序算法的伪代码如下：
For i from 0 to n–1 Find smallest number between numbers[i] and numbers[n-1] Swap smallest number with numbers[i]总结这些步骤，第一次遍历列表需要
n - 1步。第二次需要n - 2步。将此逻辑继续推导，所需步数可表示如下：(n - 1) + (n - 2) + (n - 3) + ... + 1
这可简化为 n(n-1)/2，或更简单地表示为 \(O(n^2)\)。在最坏情况或上界中，选择排序的阶为 \(O(n^2)\)。在最好情况或下界中，选择排序的阶为 \(\Omega(n^2)\)。
4.1.9. 冒泡排序¶
冒泡排序 是另一种排序算法，它通过反复交换元素将较大的元素“冒泡”到末尾。
冒泡排序的伪代码如下：
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) \times (n - 1)\)
\(n^2 - n - n + 1\)
\(n^2 - 2n + 1\)
或者更简单地表示为 \(O(n^2)\)。
在最坏情况或上界中，冒泡排序的阶为 \(O(n^2)\)。在最好情况或下界中，冒泡排序的阶为 \(\Omega(n)\)。
你可以 visualize 这些算法的比较。
4.1.10. 递归¶
我们如何改进排序的效率？
递归 是编程中的一个概念，指函数调用自身。我们之前看到过……
If no doors left 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请注意，我们正在对越来越小的问题迭代调用
search。同样，在第 0 周的伪代码中，你可以看到递归的实现位置：
1 Pick up phone book 2 Open to middle of phone book 3 Look at page 4 If person is on page 5 Call person 6 Else if person is earlier in book 7 Open to middle of left half of book 8 Go back to line 3 9 Else if person is later in book 10 Open to middle of right half of book 11 Go back to line 3 12 Else 13 Quit
此代码可以简化如下，以突出其递归特性：
1 Pick up phone book 2 Open to middle of phone book 3 Look at page 4 If person is on page 5 Call person 6 Else if person is earlier in book 7 Search left half of book 9 Else if person is later in book 10 Search right half of book 12 Else 13 Quit
基本情况 被定义为阻止递归无限继续、防止死循环的条件。
递归情况 被定义为递归函数中通过修改输入调用自身、从而向基本情况推进的部分。
考虑一下我们在第 1 周希望创建如下金字塔结构的方式：
# ## ### ####
在终端窗口中输入
code iteration.c，并按如下方式编写代码：// Draws a pyramid using iteration #include <cs50.h> #include <stdio.h> void draw(int n); int main(void) { // Get height of pyramid int height = get_int("Height: "); // Draw pyramid draw(height); } void draw(int n) { // Draw pyramid of height n for (int i = 0; i < n; i++) { for (int j = 0; j < i + 1; j++) { printf("#"); } printf("\n"); } }
请注意，此代码通过循环构建金字塔。
要使用递归实现此功能，请在终端窗口中输入
code recursion.c，并编写如下代码：// Draws a pyramid using recursion #include <cs50.h> #include <stdio.h> void draw(int n); int main(void) { // Get height of pyramid int height = get_int("Height: "); // Draw pyramid draw(height); } void draw(int n) { // If nothing to draw if (n <= 0) { return; } // Draw pyramid of height n - 1 draw(n - 1); // Draw one more row of width n for (int i = 0; i < n; i++) { printf("#"); } printf("\n"); }
注意，基本情况将确保代码不会无限运行。行
if (n <= 0)终止了递归，因为问题已得到解决。每次draw调用自身时，它都会使用n-1调用自身。在某个时刻，n-1将等于0，导致draw函数返回，程序结束。
4.1.11. 归并排序¶
我们现在可以在寻找更高效排序算法的过程中利用递归，实现称为 归并排序 的非常高效的排序算法。
归并排序的伪代码相当简短：
If only one number Quit Else Sort left half of numbers Sort right half of numbers Merge sorted halves考虑以下数字列表：
6341
首先，归并排序会问：“这是一个数字吗？”答案是“否”，因此算法继续执行。
6341
其次，归并排序现在会将数字从中间（或尽可能接近中间的位置）分开，并对左半部分的数字进行排序。
63|41
第三，归并排序会查看左侧的这些数字并询问：“这是一个数字吗？”由于答案是否定的，它会将左侧的数字从中间再次拆分。
6|3
第四，归并排序会再次询问：“这是一个数字吗？”这次答案是肯定的！因此，它将退出当前任务，返回到此刻正在运行的上一个任务：
63|41
第五，归并排序将对左侧的数字进行排序。
36|41
现在，我们回到伪代码中暂停的位置，此时左侧已排序。对右侧数字将执行类似的步骤 3-5。这将得到：
36|14
现在两半都已排序。最后，算法将合并两侧。它会查看左侧的第一个数字和右侧的第一个数字。它会先放置较小的数字，然后放置第二小的数字。算法将对所有数字重复此过程，结果为：
1346
归并排序已完成，程序退出。
归并排序是一种非常高效的排序算法，其最坏情况为 \(O(n \log n)\)。最好情况仍然是 \(\Omega(n \log n)\)，因为该算法仍然必须访问列表中的每个位置。因此，归并排序也是 \(\Theta(n \log n)\)，因为最好情况和最坏情况相同。
最后共享了一个 visualization 。
4.1.12. 总结¶
在本课中，你学习了算法思维并构建了自己的数据类型。具体来说，你学到了……
算法。
大 O 记号。
二分查找和顺序查找。
各种排序算法，包括冒泡排序、选择排序和归并排序。
递归。
下次再见！
