本文件内容源自麻省理工学院开放课程资料平台，根据官方英文讲义翻译而成，由 ChatGPT 初步翻译，并经人工精校润色。打印版参见：https://linmoh.github.io/mit6.006/l1.html

算法导论：6.006

麻省理工学院

讲师：Erik Demaine、Jason Ku 和 Justin Solomon

讲座 1：导论

本课程的目标是教会你如何解决计算问题，并说明你的解决方案是正确且高效的。

问题

• 问题输入与正确输出之间的二元关系

• 通常不会为所有输入指定每一个正确输出（太多了！）

• 提供一个可验证的谓词（属性），正确输出必须满足它

• 6.006 研究的是大规模、通用输入空间上的问题

• 非通用：小输入实例

  • 例子：这个房间里是否有两位同生日的学生？

• 通用：任意大的输入

  • 例子：给定任意 n 位学生，是否存在一对同生日的学生？
  • 若生日只在 365 天中选，对于 n > 365，根据鸽巢原理，答案一定为真
  • 假设生日的精度超过 n（包含年份、时间等）

算法

• 一个过程：将每个输入映射到一个输出（确定性）

• 若算法对每个问题输入都返回正确输出，则称其解决了该问题

• 例子：一个解决同生日问题的算法

  • 保持一个姓名和生日的记录（初始为空）
  • 按某个顺序询问每个学生 ∗ 若生日已在记录中，返回这对学生！ ∗ 否则，将姓名和生日加入记录
  • 若全部学生都询问完仍无结果，则返回 None

正确性

• 程序/算法是有限大小，如何证明其正确？

• 对于小输入，可使用情况分析

• 对于任意大的输入，算法必须以某种方式使用递归或循环

• 必须使用数学归纳法（递归在计算机科学中的关键原因）

• 例子：生日匹配算法的正确性证明

  • 对 k 归纳：记录中已有的学生数量
  • 假设：若前 k 位中有匹配，算法在询问第 k+1 位前就返回
  • 基础情况：k = 0，前 k 位无匹配
  • 假设归纳假设对 k = k₀ 成立，考虑 k = k₀ + 1
  • 若前 k₀ 位已有匹配，算法已返回（由归纳）
  • 否则，若前 k₀ + 1 位有匹配，匹配一定包含第 k₀ + 1 位
  • 那么算法直接检查第 k₀ + 1 位学生的生日是否已在记录中

效率

• 算法生成正确输出的速度有多快？

  • 可用时间测量，但希望性能不依赖于机器
  • 想法！统计算法返回前执行的固定时间操作数
  • 通常依赖输入大小：输入越大，时间越长
  • 输入大小通常称为 n，但不总是！
  • 若算法以多项式时间返回，则称其为高效
  • 有时某些问题不存在高效算法！（参见第 20 讲）

• 渐进符号（Asymptotic Notation）：忽略常数因子与低阶项

  • 上界 (O)、下界 (Ω)、紧界 (Θ)
  • 时间估计基于：1GHz 单核机器，每周期执行一次操作
  • 宇宙中的粒子数估计 < 10¹⁰⁰

计算模型

• 指定机器能以 O(1) 时间执行哪些操作

• 本课程使用的模型称为 Word-RAM

• 机器字：w 位的块（w 为字长）

• 内存：可寻址的机器字序列

• 处理器支持对 O(1) 数量的机器字执行许多 O(1) 时间操作：

  • 整数运算：(+、-、*、//、%)
  • 逻辑操作符：(&&, ||, !, ==, <, >, <=, >=)
  • 位运算：(&, |, «, », …)
  • 给定地址 a：可读取、写入地址 a 的机器字

• 内存地址必须能访问内存中所有位置

  • 要求：w ≥ 表示最大地址所需的位数，即 log₂n
  • 32 位字 → 最多约 4GB 内存
  • 64 位字 → 最多约 16EB 内存

• Python 是一个更复杂的计算模型，基于 Word-RAM 实现

数据结构

• 数据结构是一种用于存储非常量数据，并支持一组操作的方法

• 一组操作称为接口

  • Sequence（序列）：外在顺序（第一个、最后一个、第 n 个）
  • Set（集合）：内在属性排序（基于键的查询）

• 同一接口可能由不同数据结构实现，性能也不同

• 例子：静态数组（Static Array）

  • 固定宽度槽位，固定长度，静态序列接口
  • StaticArray(n)：分配大小为 n 的静态数组并初始化为 0，耗时 Θ(n)
  • StaticArray.get_at(i)：返回索引 i 处的值，耗时 Θ(1)
  • StaticArray.set_at(i, x)：将 x 写入索引 i，耗时 Θ(1)
  • 存储的机器字也可存放更大对象的地址

• 类似 Python 的 tuple 加上 set_at(i, x)

• Python list 是动态数组（详见第 2 讲）

示例代码：生日匹配

def birthday_match(students):
    '''
    找到一对同生日的学生
    输入：由 (name, bday) 元组构成的元组
    输出：学生姓名组成的元组或 None
    '''
    n = len(students)            # O(1)
    record = StaticArray(n)      # O(n)
    for k in range(n):           # n
        (name1, bday1) = students[k]  # O(1)
        # 若生日已在记录中，返回这对学生
        for i in range(k):       # k
            (name2, bday2) = record.get_at(i)  # O(1)
            if bday1 == bday2:   # O(1)
                return (name1, name2)  # O(1)
        record.set_at(k, (name1, bday1))  # O(1)
    return None                  # O(1)

示例：运行时间分析

• 两层循环：外层 k ∈ {0, …, n−1}，内层 i ∈ {0, …, k}

• 运行时间为：O(n) + ∑ₖ₌₀ⁿ⁻¹ (O(1) + k·O(1)) = O(n²)

• n 的二次方是多项式时间，算高效吗？

  • 改用其他数据结构来优化 record！

如何解决算法问题

1. 转化为你已知的问题（使用数据结构或算法）

2. 自行设计（递归）算法

   • 暴力破解
   • 减而治之
   • 分治
   • 动态规划（第 15–19 讲）
   • 贪心 / 增量法

MIT 开放式课程资料平台 https://ocw.mit.edu 6.006 《算法导论》 2020 春季学期

如需引用材料或查看使用条款，请访问： https://ocw.mit.edu/terms