【MIT6.006】lec1导论

算法导论 - 第一讲：算法与计算

一、课程介绍

• 课程名称：算法导论（Introduction to Algorithms）
• 授课教师：Jason Ku（主讲），Eric Demaine 和 Justin Solomon（共同授课）
• 课程目标：
  1. 解决计算问题。
  2. 证明算法的正确性。
  3. 论证算法的效率。
  4. 与他人沟通算法思想。

二、计算问题与算法

1. 什么是计算问题？

• 定义：计算问题可以被看作是一组输入与一组输出之间的二元关系。对于每个输入，指定哪些输出是正确的。
• 示例：
  • 在数组中查找值为 5 的索引。可能有多个索引满足条件，因此输出不唯一。
  • 在一个班级中查找是否有两个学生生日相同。如果人数超过 365，根据鸽巢原理，答案是肯定的。

2. 什么是算法？

• 定义：算法是一个固定大小的程序或过程，它将输入映射到输出，并且输出必须是正确的。
• 示例：
  • 生日问题：检查一个班级中是否有两个学生具有相同的出生时间。
    • 算法描述：
      1. 维护一个记录（存储已检查的学生生日）。
      2. 按顺序采访每个学生，询问其生日。
      3. 检查生日是否在记录中：
         • 如果在记录中，返回匹配的一对。
         • 如果不在记录中，将该学生生日加入记录。
      4. 如果检查完所有学生仍未找到匹配，返回“无匹配”。

三、算法的正确性与效率

1. 证明算法的正确性

• 方法：使用数学归纳法（Induction）。
• 示例（生日问题算法的正确性）：
  • 归纳假设：如果前 K 个学生中有匹配，算法会在采访第 K+1 个学生之前返回匹配。
  • 基础情况（Base Case）：K = 0。显然，0 个学生中不可能有匹配，假设成立。
  • 归纳步骤（Inductive Step）：
    • 如果前 K 个学生中已有匹配，则根据归纳假设，算法已返回正确结果。
    • 如果前 K 个学生中无匹配，检查第 K+1 个学生：
      • 如果第 K+1 个学生与前 K 个学生中的某个学生匹配，则算法会返回匹配。
      • 如果不匹配，则将该学生加入记录，继续检查。

2. 算法的效率

• 定义：效率不仅指算法运行的速度，还指与其他可能的解决方案相比的性能。
• 衡量方法：使用渐进分析（Asymptotic Analysis），而不是直接测量运行时间。
  • 常见时间复杂度：
    • 常数时间（O(1)）：与输入大小无关。
    • 对数时间（O(log n)）：接近常数时间。
    • 线性时间（O(n)）：与输入大小成正比。
    • 线性对数时间（O(n log n)）：接近线性时间。
    • 多项式时间（O(n^c)，c 为常数）：通常认为是高效的。
    • 指数时间（O(2^n)）：通常认为是低效的。

四、计算模型

• 模型：使用“字随机访问存储器”（Word RAM）模型。
  • 特性：
    • 内存由字（word）组成，每个字包含固定数量的比特（如 64 位）。
    • CPU 可以在常数时间内随机访问内存中的任意字。
    • 支持基本操作：整数运算、逻辑运算、内存读写等。
  • 限制：CPU 每次只能处理固定数量的信息，因此处理大量数据需要更多时间。

五、课程结构

• 第一部分（前 8 讲）：数据结构与排序。
• 第二部分：最短路径算法与图。
• 第三部分：动态规划。

六、总结

• 算法设计策略：
  1. 问题归约：将问题转化为已知问题的解决方案。
  2. 递归设计：设计递归算法解决新问题。
• 数据结构：用于存储大量数据并支持高效操作。
• 沟通与证明：能够证明算法的正确性和效率，并与他人沟通。