【笔记】CS50x 第 3 讲：算法

视频元信息

• 视频标题：哈佛大学【中英⚡计算机科学导论(2026)|CS50x Introduction to Computer Science】 p04 P5 Lecture 3 - Algorithms
• 时长：约 1 小时 50 分（本片段为 Lecture 3 完整内容）

内容摘要（TL;DR）

本讲围绕算法设计与效率分析展开：通过课堂人数统计、储物柜搜索等实例引入线性搜索与二分搜索，正式讲解大O、Ω、Θ渐近符号；随后介绍选择排序、冒泡排序与归并排序，并用递归实现马里奥金字塔；最后通过可视化对比各算法运行时间，强调算法设计对效率的决定性影响。

一、开场：课堂人数统计算法

[时间戳 134s-512s]

1.1 三种计数算法的实际演示

• 教授在课堂上让学生们用不同算法统计教室人数：

  • 算法一：逐个计数（Kelly 手动一个个数）→ 线性时间
  • 算法二：两人一组配对相加 → 仍然线性，但速度约为两倍
  • 算法三：分治配对——每人先持有数字1，然后一半人把自己的数字交给另一半人，如此反复，最终汇聚到一个人手中 → 对数时间

• 实际执行结果：分治算法得到 141 人，Kelly 手工数得约 160 人。

  • 理解：分治算法理论上更快，但实际执行中因为“人肉算术”出错（mental math bugs）导致结果偏差，这正好说明算法的正确性（correctness）与执行正确性是两回事。
  • 易错点：算法理论上正确，但执行过程中可能因人为失误产生错误结果，不能因此否定算法本身。

1.2 算法效率的直观分析

• 逐个计数：n 步，画成直线（斜率1）
• 两个两个数：约 n/2 步，仍是直线，但严格更快
• 分治配对：约 log₂n 步，人数翻倍只需多一步，人数变为四倍只需多两步
  • 推导：如果教室人数翻倍，分治算法只需额外1轮配对；人数变为4倍，只需额外2轮。这就是对数增长的威力。
• 核心结论：算法设计越巧妙，成本（时间/空间/金钱）增长越慢。

二、数组与计算机的“单门访问”模型

[时间戳 674s-763s]

2.1 数组回顾

• 数组是计算机中最简单的数据结构：内存中一块连续的区域，值一个接一个存放（back to back）。
• 上一周已经介绍了数组的基本概念，本周将在此基础上讨论算法。

2.2 计算机不能“鸟瞰”数组

• 人眼可以一眼看到整个屏幕，立刻找到数字50在哪里；但计算机不能这样。
• 计算机每次只能访问一个内存位置——相当于走到一扇关着的门前，打开门看里面的值，然后关门，再去下一扇门。
• 思考：这是理解算法复杂度的关键模型。即使人觉得“一眼就看到”，算法必须一步一步访问，因此步骤数才成为衡量标准。

2.3 零索引（Zero-indexing）

• 数组位置从 0 开始编号：locker 0, locker 1, ..., locker 6。
• 易错点：听到“location 6”意味着至少有7个元素，因为从0开始计数。 这是C语言等编程语言的通用约定。

三、线性搜索与二分搜索的实物演示

[时间戳 724s-1120s 左右]

3.1 储物柜实验

• 舞台上放置7个储物柜，里面是不同面值的 monopoly 钞票，目标是找到50美元钞票。
• 志愿者 Jose：从左到右依次打开每个柜子，逐个检查。
  • 他的算法：走到第一个门→打开→检查是否是目标→关上门→去下一个。
  • 结果：找了很久才找到50（50在最后一个柜子）。
  • 他自己也承认：如果从右端开始可能运气好一步找到，但一般情况不知道数据分布，线性扫描是最好的选择。
  • 随机跳跃查找：可能运气好，但需要额外记忆哪些门已经打开，浪费空间。
• 志愿者 Caitlin：Kelly 事先把钞票按面值从小到大排序。
  • 她的策略：从中间开始。
  • 第一次打开中间柜子：20（小于50）→ 50一定在右边。
  • 再打开右侧三个柜子的中间：100（大于50）→ 50一定在左边。
  • 再打开左侧中间：50，找到。
  • 理解：虽然演示中 Caitlin 因“已知面值范围”有直觉，但通用二分搜索确实只需 log₂n 次比较。

3.2 形式化伪代码

线性搜索（Linear Search）：

for each door from left to right:
    if 50 is behind door:
        return true
return false

• 易错点：不能写成 if-else 结构——如果在第一个门没找到就 return false，会漏掉后面所有门。正确做法是循环结束后再 return false。
• 计算机科学记号（伪代码风格）：

  for i from 0 to n-1:
        if 50 is behind doors[i]:
            return true
    return false
  

  • 注意 n-1 而不是 n：因为从0开始计数，n个元素的下标是0到n-1。

二分搜索（Binary Search）：

if no doors left:
    return false
if 50 is behind middle door:
    return true
else if 50 < middle door value:
    search left half
else if 50 > middle door value:
    search right half

• 关键细节：
  • 搜索左半部分时，范围是 doors[0] 到 doors[middle-1]，而不是 doors[middle]——因为中间门已经检查过。
  • 搜索右半部分时，范围是 doors[middle+1] 到 doors[n-1]。
  • 需要先检查“没有门可搜”的边界情况（base case），否则会无限递归。
• 中间下标计算：n=7 时，7/2=3.5，向下取整为3，即 doors[3] 是中间元素。

3.3 为什么二分搜索要求数据有序

• 易错点：在未排序数组上使用二分搜索是错误用法——因为比较大小后决定向左/向右，但数据无序时，左右两边没有大小规律，会做出错误决策，很可能直接错过目标。
• 思考：排序是二分搜索的前提，但排序本身也有成本，是否值得排序取决于搜索次数。

四、渐近符号：Big O, Ω, Θ

[时间戳 1120s-1400s 左右]

4.1 运行时间的图形分析

• 三种计数算法画成图：
  • 线性：n 步 → 直线
  • 每次两个：n/2 步 → 直线但更陡（更快）
  • 分治：log₂n 步 → 曲线增长极慢
• 计算机科学家不关心精确步骤数，只关心“量级”（order of），因此使用 Big O 符号。

4.2 Big O（大O）：上界

• Big O 描述算法在最坏情况下（或作为上界）步骤数随 n 增长的量级。
• 常见 Big O 运行时间（由慢到快）：
  • O(n²) —— 平方级
  • O(n log n) —— n 乘以 log n
  • O(n) —— 线性
  • O(log n) —— 对数
  • O(1) —— 常数
• 规则：忽略低阶项，只关注主导项（dominant term）。
  • 例如 O(n/2) 写作 O(n)，因为常数因子不影响增长趋势。
  • O(log₂n) 写作 O(log n)，底数不重要。
• 线性搜索：O(n)（最坏情况目标在最后）
• 二分搜索：O(log n)（每次排除一半）

4.3 Omega（Ω）：下界

• Omega 描述算法在最好情况下（或作为下界）至少需要多少步。
• 线性搜索：Ω(1)——运气好第一个门就是目标。
• 二分搜索：Ω(1)——运气好目标正好在中间。
• 理解：上下界共同给出了算法性能的可能范围。

4.4 Theta（Θ）：紧界

• Theta 当 Big O 和 Omega 相同时使用，表示算法运行时间被精确界定。
• 目前讨论的线性搜索、二分搜索都不能用 Θ，因为它们的上下界不同。

4.5 渐近符号的意义

• 推导：当 n 很大时，O(n²) 与 O(n log n) 的差距巨大。例如 n=10⁹，n²=10¹⁸，n log n≈3×10¹⁰，相差数亿倍。
• 设计决策：如果只搜索一次数据，排序再二分可能不如直接线性搜索；如果反复搜索（如 Google），排序成本可以摊还（amortize）。

五、C语言实现：线性搜索与字符串比较

[时间戳 1400s-1900s 左右]

5.1 整数数组的线性搜索

• 在 VS Code 中编写 search.c：
  • 初始化数组 int numbers[] = {20, 5, 100, 10, 5, 1, 50};（用花括号静态初始化，编译器自动计数长度）
  • 用 get_int 获取用户要查找的数字
  • 用 for 循环遍历数组，if (numbers[i] == n) 则打印 found 并 return 0（成功退出码）
  • 循环结束后打印 not found 并 return 1（失败退出码）
• 易错点：main 函数返回 int 作为退出状态，0 表示成功，非0表示出错。

5.2 字符串比较的陷阱

• 将代码改为搜索字符串数组（battleship, boot, cannon, iron, thimble, top hat）时，直接用 == 比较字符串会失败，即使字符串明明在数组中。
• 原因：字符串不是单个值，而是多个字符的序列。== 比较的是字符串的地址（指针），而不是内容。
• 解决方法：使用 strcmp 函数（来自 string.h）：

  if (strcmp(strings[i], s) == 0) { ... }
  

• 易错点：strcmp 返回 0 表示两个字符串相等，而不是返回 true/false。它返回负数/正数表示字典序（实际上是 ASCII 序）的前后关系，这为将来排序提供了便利。
• 易错点：使用 strcmp 必须 #include <string.h>，否则编译器报错“call to undeclared library function”。

5.3 电话簿示例：从平行数组到结构体

• 最初用两个平行数组：names[] 和 numbers[]，通过相同下标关联。
  • 缺点：依赖“君子协定”保证两个数组长度一致、顺序对应，容易出错。
  • 思考：如果数组有30个人，手动维护两个数组的对应关系很容易出错，这是“信任自己/同事”的坏味道。
• 改进：使用 typedef struct 自定义数据类型：

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

  • 然后创建 person people[3];，用点号访问字段：people[0].name = "Kelly"; people[0].number = "+1-617-495-1000";
  • 这样把相关数据“封装”在一起，避免平行数组的对齐问题。
• 为什么电话号码用字符串而不用整数：
  • 电话号码包含 +、-、括号等非数字字符。
  • 如果号码有前导零（如某些国家的区号），整数会丢失前导零。
  • 理解：凡是可能包含非数字字符或需要保留前导零的“编号”，都应该用字符串存储。

六、排序算法：选择排序与冒泡排序

[时间戳 1900s-2600s 左右]

6.1 排序问题的定义

• 输入：未排序的数据（如 7 2 5 4 1 6 0 3）
• 输出：排序后的数据（如 0 1 2 3 4 5 6 7）
• 课堂上用8名志愿者手持数字牌模拟排序。

6.2 选择排序（Selection Sort）

• 算法思想：每次从剩余元素中选出最小元素，放到正确位置。
• 伪代码：

  for i from 0 to n-1:
        find smallest number between numbers[i] and numbers[n-1]
        swap it with numbers[i]
  

• 演示过程：
  • 第一轮：扫描全部8个数字，记住最小值0，与位置0的7交换。
  • 第二轮：扫描剩下7个数字，记住最小值1，与位置1的2交换。
  • 继续直到全部排好。
• 分析运行时间：
  • 第一轮比较 n-1 次，第二轮 n-2 次，...，最后一轮1次。
  • 总比较次数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2
  • 展开 = n²/2 - n/2 → 忽略低阶项 → O(n²)
  • 即使数据已经有序，选择排序仍然要执行相同的比较次数，所以 Ω(n²)，因此 Θ(n²)。
  • 结论：选择排序无论数据是否有序，运行时间都是 Θ(n²)，非常慢。

6.3 冒泡排序（Bubble Sort）

• 算法思想：反复比较相邻元素，如果顺序错误就交换，每一轮把当前最大元素“冒泡”到末尾。
• 伪代码：

  repeat n-1 times:
        for i from 0 to n-2:
            if numbers[i] and numbers[i+1] are out of order:
                swap them
  

• 易错点：内层循环到 n-2 而不是 n-1，因为要访问 i+1，防止数组越界。
• 演示过程：7与2交换，7与5交换，7与4交换... 7一路“冒泡”到最右端；然后6冒泡到倒数第二，依此类推。
• 分析运行时间：
  • 外层循环 n-1 次，内层循环 n-1 次 → 总步骤约 (n-1)² = n² - 2n + 1 → O(n²)
  • 优化：如果在某一轮遍历中没有发生任何交换，说明列表已经有序，可以提前终止。
  • 加入优化后，最好情况（数据已有序）只需遍历一次，做 n-1 次比较 → Ω(n)
  • 由于 O(n²) 和 Ω(n) 不同，不能使用 Θ。
  • 理解：冒泡排序的优化只在“基本有序”时有效，平均/最坏仍是 O(n²)。

6.4 可视化对比

• 使用动画演示选择排序和冒泡排序：紫色竖条高度代表数值大小。
• 选择排序：每轮找最小，逐步固定左侧，但右侧元素要等很久。
• 冒泡排序：相邻比较交换，最大元素逐步“冒泡”到右侧。
• 两者在几十个元素时已经明显耗时，n 很大时更是不可接受。
• 结论：需要更快的排序算法。

七、递归（Recursion）

[时间戳 2600s-3200s 左右]

7.1 递归的定义

• 递归函数：一个函数在定义中调用自身（数学上：f(x) 的定义依赖于 f(某表达式)）。
• 递归最容易引发的问题是无限循环——函数不断调用自己，永不停止。
• 解决方案：必须有一个基准情形（base case），直接给出答案，不再递归。

7.2 二分搜索中的递归

• 回顾二分搜索伪代码中的“search left half”和“search right half”——这就是递归调用。
• 每次递归调用处理更小的问题（一半的数据），因此最终会到达基准情形（没有门可搜）。
• 理解：递归不是简单地重复同样的问题，而是把问题规模不断缩小，直到可以直接解决。

7.3 递归定义马里奥金字塔

• 高度为4的金字塔 = 高度为3的金字塔 + 一行4个砖块。
• 高度为3的金字塔 = 高度为2的金字塔 + 一行3个砖块。
• 高度为2的金字塔 = 高度为1的金字塔 + 一行2个砖块。
• 高度为1的金字塔 = 一个砖块（基准情形）。

7.4 迭代实现 vs 递归实现

• 迭代版本（iteration.c）：

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

  • 外层循环控制行，内层循环控制每行的砖块数（i+1 是因为第0行要1个砖块）。

• 递归版本（recursion.c）：

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

  • 先画高度 n-1 的金字塔，再画最后一行 n 个砖块。
  • 必须加上 if (n <= 0) return; 基准情形，否则 clang 会报错“all paths through this function will call itself”，拒绝编译。
  • 使用 <= 0 而不是 == 0 是为了处理负数输入（防御性编程）。

7.5 递归的代价：栈溢出

• 演示中输入非常大的高度（如 100000），程序崩溃，出现 segmentation fault 或类似错误。
• 原因：每次调用 draw 都会占用一定的内存（栈帧），递归调用太深会耗尽计算机内存。
• 迭代版本不会出现此问题，因为它不额外占用调用栈。
• 思考：递归代码更优雅、更简洁，但牺牲了内存；这是“时间/空间/优雅”之间的权衡。

八、归并排序（Merge Sort）

[时间戳 3200s-3800s 左右]

8.1 归并排序的伪代码

sort left half of numbers
sort right half of numbers
merge sorted halves

• 基准情形：如果只剩一个元素，它已经有序，直接返回。
• 关键在于“合并”（merge）两个已排序的数组。

8.2 合并过程演示

• 假设左半 [1,3,4,6] 和右半 [0,2,5,7] 都已排序。
• 用两个指针分别指向左半开头和右半开头，比较两者，把较小的放到结果数组顶部。
• 每一步只移动一个指针，每个元素只被比较一次。
• 合并 n 个元素需要 n 步。

8.3 归并排序的完整过程

• 对 [6,3,4,1,5,2,7,0] 排序：
  1. 排序左半 [6,3,4,1]：
     • 排序左半 [6,3]：排序左半 [6]（基准），排序右半 [3]，合并 → [3,6]
     • 排序右半 [4,1]：排序左半 [4]，排序右半 [1]，合并 → [1,4]
     • 合并 [3,6] 和 [1,4] → [1,3,4,6]
  2. 排序右半 [5,2,7,0]：类似 → [0,2,5,7]
  3. 合并 [1,3,4,6] 和 [0,2,5,7] → [0,1,2,3,4,5,6,7]
• 整个过程只进行了约 log₂n 层“分治”，每层合并总共 n 步。

8.4 归并排序的运行时间

• 把大小为8的列表排序：分成3层（log₂8=3），每层合并8个元素 → 总步骤约 n log n。
• Big O：O(n log n)
• Omega：Ω(n log n)（没有类似冒泡排序的提前终止优化）
• 因此 Theta：Θ(n log n)
• 推导：n=8 时 log₂8=3；n=1024 时 log₂1024=10；n 越大，n log n 比 n² 的优势越明显。
• 注意：归并排序需要额外的内存空间来存放合并结果（演示中用了第二个架子），这是它的代价。

8.5 可视化对比

• 在动画中点击 merge sort，可以看到明显的速度提升：它不像选择/冒泡排序那样反复比较同一批元素，而是分而治之，每层只做少量工作。
• 最终演示：同时运行选择排序、冒泡排序、归并排序，归并排序最先完成，凸显 O(n log n) 与 O(n²) 的实际差距。

九、总结与关键结论

• 算法的正确性和设计同样重要。
• 渐近符号（Big O / Ω / Θ）是描述算法效率的标准语言。
• 线性搜索 O(n)、二分搜索 O(log n)（需有序数据）。
• 选择排序 Θ(n²)、冒泡排序 O(n²)/Ω(n)、归并排序 Θ(n log n)。
• 递归是一种强大的问题解决技术，但必须注意基准情形和内存开销。
• 设计决策：根据数据规模、搜索/排序频率、可用内存等权衡不同算法。

关键标签/关键词

算法 Algorithms 线性搜索 二分搜索 Big O Omega Theta 渐近符号 选择排序 冒泡排序 归并排序 递归 数组 字符串比较 strcmp 结构体 typedef struct 运行时间 分治 CS50 Lecture 3

生成时间：2026-09-02 17:14:31 生成平台：VideoNote