CS50 Week 3 Algorithms¶

算法基础知识。

搜索¶

计算机没办法一眼看到所有的数据，然后告诉我们哪个元素在哪个位置。

一个简单的搜索问题：输入一些值，输出一个布尔值，来表示"一个特定的值是否在这些输入的值当中"。

Big \(O\)¶

不同算法的效率不同。
\(O\)代表"On the order of"，可以理解为一个算法最多（也就是在最坏的情况下）要执行多少步。
\(\Omega\)可以理解为一个算法最少（也就是在最好的情况下）要执行多少步。
如果一个算法执行时间的上限和下限是一样的，可以用\(\Theta\)来表示。

线性搜索和二分搜索¶

线性搜索就是一个一个地查看内存中的值，判断这个值是否为我们想找的。如果是，则返回"找到了"；如果不是，则继续查找下一个。直到查看了最后一个元素，若仍然没有找到想要的元素，则返回"没找到"。
线性搜索：
- \(O(n)\)：最多需要搜索\(n\)次。
- \(\Omega(1)\)：最少只需要搜索\(1\)次。
要实现二分搜索，需要确保数据是按大小排序的。
二分搜索：
- \(O(\log n)\)
- \(\Omega(1)\)

使用`C`进行线性搜索¶

搜索字符串的代码：

C

#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;
}

上面的代码会报错：

Bash

$ 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不能用==来判断两个字符串是否相等。

正确的方法是用string.h中的函数：

if (strcmp(names[i], "Ron") == 0)
- `strcmp(names[i], "Ron")如果是 0，说明两个字符串是一样的。
- 可以查看strcmp的手册说明

数据结构¶

一个规范的数据结构可以方便管理数据，确保数据的组织方式是符合预期的。

C

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

//定义数据结构。
typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[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;
}

C不是面向对象的。上面的数据结构只能定义数据的组织方式，但不能包含函数。

排序¶

选择排序¶

思路：
- 找到数组中最小的数字，把它和数组中的第 1 个元素交换位置。
- 找到数组中第 2 小的数字，把它和数组中的第 2 个元素交换位置。
- 以此类推。每完成一步，我们的 Problem size 都减小了 1。
最坏的情况：
- 每一轮要找的最小的数字都在数组的最后一个，因此，找第 1 轮需要\(n\)次运算，找第 2 轮需要\(n-1\)次运算（因为 Problem size 减小到\(n-1\)了），找第\(n-1\)轮需要\(2\)次运算。
- \[ \begin{aligned} &n+\left( n-1\right) +\left( n-2\right) +\dots +1 \\\ &=\frac{n\left( n+1\right) }{2} \\\ &=\frac{n^2}{2}+\frac{n}{2} \end{aligned} \]
- 按阶数来看，低阶的\(\frac{n}{2}\)可以忽略，因为当\(n\)很大时，低阶项已经不起主导作用了。
- 为了表示起来简便，虽然高阶项的系数是\(1\over 2\)，但我们仍然把复杂度记作\(O(n^2)\)。
最好的情况：
- 虽然原始的数组已经是排序过的了。
- 但选择算法仍然会不停地对比，才能找到最小的那个数。
- 比如数组[1, 2, 3, 4, 5]，虽然最小的数 1 已经在最前面了，但计算机不确定 1 后面是否还有比 1 更小的数字，所以仍然会一个一个地搜索。
- 总搜索次数是\(\frac{n^2}{2}+\frac{n}{2}\)，所以最好的情况复杂度仍然是\(O(n^2)\)。

冒泡排序¶

思路：
- 每次只对比相邻的两个数字，把它们从小到大排序。
最坏的情况：
- 第 1 步中，从左到右全部扫描一遍，需要对比\((n-1) 次\)。
- 每进行一次第 1 步，我们就可以把一个比较大的数字移到最右边。具体来说：进行 1 次第一步，我们可以保证最大的数字一定在最右边；进行 2 次第一步，我们可以保证前 2 大的数字一定在最右边；以此类推。
- 最多要进行\((n-1)\)次第 1 步，就能保证所有的数字都是正确排序的。
- 下面是粗略的计算：
- \[ \begin{aligned} &(n-1)(n-1)\\\ &=n^2-2n+1 \end{aligned} \]
- 时间复杂度记为\(O(n^2)\)。
最好的情况：
- 首先，对上述步骤进行改进：加上最后两行，如果没有发生交换，说明已经是排好序的了，即可结束程序。
Text Only
```
  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)\)次，发现没有需要交换的，就结束程序了。因此最好的情况可以做到\(\Omega(n)\)。

递归¶

在函数内部继续调用函数本身。
在写递归函数的时候，要注意定义清楚 Basic case，否则会一直递归下去，没有终点。

合并排序¶

思想：
- 要对一个长度不为 1 的数组进行排序，可以分成 3 步：
  - 先对左半边进行排序；
  - 再对右半边进行排序；
  - 最后将左半边和右半边的排序结果进行合并。合并的具体过程是：比较左半边的第 1 个和右半边的第 1 个，把最小的那个提取出来。不断继续这个过程即可。
- 要对一个长度为 1 的数组进行排序，则这个数组本身就是排好序的。
最坏的情况：
- 把一个数组不断地分成两半，最多一共要分\(\log n\)次。这意味着，最多要进行\(\log n\)层"合并"。
- 每一层合并都需要比较\(n\)次。
- 因此，最多一共需要\(n\log n\)次比较运算，即\(O(n \log n)\)。
最好的情况：
- 仍然需要进行\(n\log n\)次比较运算，即\(\Omega(n \log n)\)。
注意：
- 合并排序法在时间复杂度上占优，但它需要额外的内存空间，用于储存临时合并好的数组。
- 搜索排序和冒泡排序可以在原始的数组内存空间上进行元素交换，不需要额外的内存空间。