视频封面

  • 时长: 未提供（原转录文本未包含总时长）
  • 时间戳说明：视频前段使用转录中提供的准确时间戳；14:46 之后的部分根据内容推进估算，用 ~ 标记。

TL;DR

CS50 第三讲围绕算法设计及效率分析，复习并实现了线性搜索、二分查找，介绍大 O/Ω/Θ 渐近记号，并用 C 语言实现数组和结构体搜索；之后详细讲解选择排序、冒泡排序、递归与归并排序，通过可视化对比各算法实际性能。

Introduction and Recap: The Phone Book [01:17]

  • 课程进入第 3 周，主题完全聚焦于 算法（algorithms）。
  • 回顾第 0 周电话簿搜索 John Harvard 的例子：
    1. 一次翻一页：完全正确但非常慢，运行时间是一条直线，即 O(n)；
    2. 一次翻两页：约快一倍，但如果 John 被夹在中间需要回退一页，系数变小但仍是线性；
    3. 分而治之（divide and conquer）：即今天要命名的 二分查找，每次把问题对半切。
  • 书中关键结论：若城市合并使电话簿从 1000 页变成 2000 页，二分查找只需要多撕一次就能继续大幅缩小问题。
  • 本周目标：不仅正确实现算法，还要关注设计（design）与效率（efficiency）。
  • 不会引入太多 C 语言新语法，只补充一些解决具体问题的积木，例如 string.h 和结构体。

Memory, Arrays, and the Search Problem [04:43]

  • 电脑内存（RAM）表现为一块黑色芯片，例如 1 GB ≈ 10 亿字节 / 80 亿比特。
  • 内存可被“编址”：从 byte 0、1、2……一直到 byte n-1，因此我们能以统一方式访问内存。
  • 把内存抽象成画布，每个方格代表 1 字节；上周我们把数据划分成 数组（array）。
  • 数组关键属性：元素在内存中连续存放（contiguous）——这一布局是本周高效算法的基础。
  • 模型：电脑一次只能查看一个内存位置（虽然不是绝对，但可作为简化模型）。
  • 用 7 个“门／储物柜”表示

生成时间：2026-09-11 13:08:31 生成平台：VideoNote www.xygy.top