Week 3 算法
欢迎！
在第 0 周，我们介绍了算法这个概念：它就像一个黑盒，可以接收输入并产生输出。
本周，我们将通过伪代码进一步理解算法，并逐步进入真正的代码实现。
同时，我们也会思考这些算法的效率。事实上，我们会在上周讨论过的一些概念基础上，继续学习如何用它们来构建算法。
回想课程前面介绍过的这张图：
进入本周时，你应该思考：算法处理问题的方式，可能会决定解决问题所需的时间！算法可以被设计得越来越高效，但这种高效也有其极限。
今天，我们会重点关注算法的设计，以及如何衡量算法的效率。
线性搜索
- 回想上周，我们介绍过数组的概念：数组是连续的一块块内存，也就是彼此相邻、挨在一起的内存空间。
你可以把数组形象地想象成一排七个红色储物柜，如下所示：
最左边的位置称为位置 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
请注意，上面仍然不是代码，但已经非常接近最终代码可能呈现的样子。
二分搜索
二分搜索是另一种搜索算法，也可以用于寻找数字 50。
假设储物柜中的值已经从小到大排列好，二分搜索的伪代码会像这样：
If no doors left
Return false
If 50 is behind middle door
Return true
Else if 50 middle door
Search right half
使用更接近代码的命名方式，我们可以进一步修改算法如下：
If no doors left
Return false
If 50 is behind doors[middle]
Return true
Else if 50 doors[middle]
Search doors[middle + 1] through doors[n - 1]
请注意，看到这段接近代码的表达时，你几乎已经能想象它在真实代码中会是什么样子。
运行时间
- 你可以思考一个算法解决问题需要多长时间。
运行时间通常使用 big O 表示法来分析。请看下面这张图：
计算机科学家讨论效率时，通常不会过分精确到每一个数学细节，而是用不同运行时间的数量级来描述效率。
在上图中，第一个算法是 \(O(n)\)，也就是 n 的数量级。第二个同样是 \(O(n)\)。第三个是 \(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\) 符号用于表示上界和下界相同的情况：也就是最好情况和最坏情况的运行时间相同。
渐近表示法用于衡量当输入越来越大时，算法表现得有多好。
- 随着你继续学习计算机科学，你会在后续课程中更深入地探索这些主题。
search.c
你可以在终端窗口中输入 code search.c，并编写如下代码来实现线性搜索：
// Implements linear search for integers
#include
#include
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
#include
#include
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 是硬编码的，这并不是良好的编程习惯。
运行这段代码确实可以让我们遍历这个字符串数组，查看某个字符串是否在其中。不过，如果你遇到段错误，也就是程序访问了它不该访问的内存位置，请确认上面写的是
i < 6，而不是i < 7。你可以在 CS50 Manual Pages 上了解更多关于
strcmp的信息。
phonebook.c
我们可以把数字和字符串这两个想法结合到一个程序中。在终端窗口中输入 code phonebook.c，并编写如下代码：
// Implements a phone book without structs
#include
#include
#include
int main(void)
{
// Arrays of strings
string names[] = {"Yuliia", "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;
}
请注意，Yuliia 的号码以 +1-617 开头，David 的电话号码也以 +1-617 开头，而 John 的号码以 +1-949 开头。因此，names[0] 是 Yuliia，numbers[0] 是 Yuliia 的号码。这段代码允许我们在电话簿中搜索某个人的具体号码。
虽然这段代码可以工作，但它存在不少低效之处。事实上，姓名和电话号码之间有可能不再对应。如果我们能创建自己的数据类型，把一个人和电话号码关联起来，岂不是更好？
结构体
- 原来，C 允许我们通过
struct创建自己的数据类型。
创建一个名为 person 的自定义数据类型，让它内部包含 name 和 number，是不是会很有用？请看下面的代码：
typedef struct
{
string name;
string number;
} person;
请注意，这表示我们自己的数据类型 person，它包含一个名为 name 的字符串，以及另一个名为 number 的字符串。
我们可以把之前的电话簿程序修改如下，从而改进代码：
// Implements a phone book with structs
#include
#include
#include
typedef struct
{
string name;
string number;
} person;
int main(void)
{
person people[3];
people[0].name = "Yuliia";
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，并为这个人指定姓名。
排序
排序是把一个未排序的值列表转换为有序列表的过程。
当列表已经排好序时，搜索这个列表对计算机来说会轻松得多。回想一下，我们可以在有序列表上使用二分搜索，但不能在无序列表上这样做。
事实上，排序算法有很多不同类型。
选择排序就是其中一种排序算法。
我们可以把数组表示如下：
选择排序算法的伪代码是：
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)\)。
冒泡排序
冒泡排序是另一种排序算法，它通过反复交换元素，让较大的元素“冒泡”到末尾。
冒泡排序的伪代码是：
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) × (n – 1)
n2 – 1n – 1n + 1
n2 – 2n + 1
或者更简单地表示为 \(O(n^2)\)。
在最坏情况或上界中，冒泡排序的数量级是 \(O(n^2)\)。在最好情况或下界中，冒泡排序的数量级是 \(\Omega(n)\)。
你可以通过这个可视化比较这些算法。
递归
- 我们如何提高排序的效率？
递归是编程中的一个概念，指一个函数调用它自身。我们之前已经见过这种思想，比如：
If no doors left
Return false
If number behind middle door
Return true
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
#include
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 iteration.c，并编写如下代码：
// Draws a pyramid using recursion
#include
#include
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 函数返回，程序结束。
归并排序
- 现在，我们可以在追求更高效排序算法的过程中利用递归，并实现一种称为归并排序的高效排序算法。
归并排序的伪代码非常简短：
If only one number
Quit
Else
Sort left half of number
Sort right half of number
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)\)，因为最好情况和最坏情况相同。
课程中还分享了最后一个可视化。
总结
在本课中，你学习了算法思维以及如何构建自己的数据类型。具体来说，你学习了……
算法。
Big O 表示法。
二分搜索和线性搜索。
多种排序算法，包括冒泡排序、选择排序和归并排序。
递归。
下次见！