讲座 3

欢迎!
线性搜索
二分搜索
运行时间
search.c
phonebook.c
结构体
排序与选择排序
冒泡排序
递归
归并排序
总结

欢迎!

在第零周，我们介绍了算法的概念：一个接受输入并产生输出的黑匣子。
本周，我们将通过伪代码进一步扩展对算法的理解，并进入实际代码。
同时，我们还将考虑这些算法的效率。实际上，我们将基于之前讨论过的一些概念，进一步构建对算法的理解。
考虑以下图表：
算法可能很慢，具有较高的时间和处理成本；也可能很快，具有较低的处理和时间成本。
进入本周，你应该考虑算法处理问题的方式如何决定解决问题所需的时间！算法可以被设计得越来越高效，直至达到一个极限。
今天，我们将关注算法的设计以及如何衡量它们的效率。

线性搜索

回想一下上周，你了解了数组的概念：内存中连续、一个接一个排列的区块。
你可以形象地将数组想象成一排七个红色的储物柜，如下所示：

[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
```
注意，以上内容还不是代码，但它已经非常接近最终代码的样子了。

二分搜索

二分搜索是另一种可以用于查找数字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

使用代码的术语，我们可以进一步修改我们的算法如下：

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]

注意，通过观察这段近似代码，你几乎可以想象出它在实际代码中会是什么样子。

运行时间

你可以考虑一个算法解决一个问题需要多少时间。
运行时间涉及使用大O符号进行分析。请看下图：
计算机科学家讨论算法效率时，不是极端具体地讨论其数学效率，而是用各种运行时间的阶来描述。
在上图中，第一个算法是 O(n) 或n 阶。第二个算法也是 O(n)，因为大 O 表示法中常数项被省略了。第三个是 O(log n)。
曲线的形状显示了算法的效率。我们可能会看到的一些常见运行时间有：
- O(n²)
- O(n log n)
- O(n)
- O(log n)
- O(1)
在上述运行时间中，O(n²) 被认为是最慢的运行时间，O(1) 是最快的。
线性搜索的阶是 O(n)，因为最坏情况下可能需要 n 步才能运行完成。
二分搜索的阶是 O(log n)，因为它即使在最坏情况下也只需要越来越少的步骤。
程序员既关心最坏情况（上界），也关心最好情况（下界）。
Ω 符号用于表示算法的最好情况，例如 Ω(log n)。
Θ 符号用于表示上界和下界相同的情况：即最好情况和最坏情况运行时间相同。
渐近符号用于衡量算法在输入越来越大时的表现。
随着你在计算机科学领域的知识不断深入，你将在未来的课程中更详细地探索这些主题。

search.c

你可以通过在终端窗口中输入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循环中，我们实现了线性搜索。返回 0用于表示成功并退出程序。返回 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是硬编码的，这不是好的编程实践。

实际上，运行这段代码允许我们遍历这个字符串数组，看看某个特定的字符串是否在其中。但是，如果你看到段错误——即你的程序访问了不应该访问的内存区域——请确保你写的是i < 6而不是i < 7。
你可以在CS50 手册页面了解更多关于strcmp的信息。

phonebook.c

我们可以将数字和字符串的概念结合到一个程序中。在你的终端窗口中输入code phonebook.c并编写如下代码：

// Implements a phone book without structs

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

int main(void)
{
    // 数组 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 的电话号码。这段代码将允许我们在电话簿中搜索某个人的特定号码。

虽然这段代码能工作，但存在很多低效之处。实际上，名字和电话号码有可能不对应。如果我们能创建自己的数据类型，将一个人与其电话号码关联起来，那岂不是很好？

结构体

事实证明，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的字符串。在main函数中，我们首先创建了一个名为people的数组，其类型为person，大小为3。然后，我们更新了people数组中三个人的姓名和电话号码。最重要的是，注意点号表示法（例如people[0].name）如何允许我们访问第0个位置的person并给该个体分配一个名字。

排序与选择排序

排序是将未排序的值列表转换为已排序列表的行为。
当列表排序后，搜索该列表对计算机的负担要小得多。回想一下，我们可以在已排序的列表上使用二分搜索，但不能在未排序的列表上使用。
事实证明，有很多不同类型的排序算法。
选择排序就是其中一种排序算法。
我们可以将数组表示如下：

[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²)。在最坏情况或上界中，选择排序的阶为 O(n²)。在最好情况或下界中，选择排序的阶为 Ω(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) \times (n - 1)
- n^2 - n - n + 1
- n^2 - 2n + 1
- 或者更简单地表示为 O(n²)。
在最坏情况或上界中，冒泡排序的阶为 O(n²)。在最好情况或下界中，冒泡排序的阶为 Ω(n)。
你可以可视化这些算法的比较。

递归

我们如何提高排序的效率？

递归是编程中的一个概念，指函数调用自身。我们之前看到过……

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周的伪代码中，你可以看到递归的实现：

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
    Open to middle of left half of book
    Go back to line 3
Else if person is later in book
   Open to middle of right half of book
   Go back to line 3
Else
   Quit

这段代码可以简化以突出其递归特性，如下所示：

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

基本情况被定义为阻止递归无限继续的条件，防止无限循环。
递归情况被定义为递归函数中调用自身的那部分，使用修改后的输入，逐步向基本情况靠近。
想想在第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函数返回，程序结束。

归并排序

我们现在可以在追求更高效的排序算法时利用递归，实现所谓的归并排序，一种非常高效的排序算法。

归并排序的伪代码非常简短：

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)。最好情况仍然是 Ω(n log n)，因为算法仍然必须访问列表中的每个位置。因此，归并排序的阶也是 Θ(n log n)，因为最好情况和最坏情况相同。
最后分享了一个可视化演示。

总结

在这节课中，你学习了算法思维和构建自己的数据类型。具体来说，你学到了……

算法.
大O符号。
二分搜索和线性搜索。
各种排序算法，包括冒泡排序、选择排序和归并排序。
递归。

下次再见！


[0]	[1]	[2]	[3]	[4]	[5]	[6]


[0]	[1]	[2]	[...]	[n-3]	[n-2]	[n-1]