算法设计与分析课程-第1讲-引言-屈婉玲
主讲：屈婉玲（北京大学） 课号：0A002 来源：田浩然上传的资料/0A002算法分析与设计/lecture1.pdf 页数：37页 格式：文字版PDF
课程基本信息
- 课程名称：算法设计与分析（Design and Analysis of Algorithms）
- 课号：0A002
- 主讲：屈婉玲（北京大学，qwl@pku.edu.cn）
课程目标
- 掌握组合算法设计的基本技术
- 掌握算法分析的基本方法
- 了解计算复杂性理论的基本概念及其应用
课程内容三大模块
| 模块 | 子主题 |
|---|---|
| 顺序算法设计的基本技术 | 分治策略、动态规划、贪心法、回溯算法、概率算法* |
| 顺序算法分析的基本方法 | 评价算法的标准、算法复杂性的估计、问题复杂性的下界、算法分析的实例 |
| 计算复杂性理论的基本概念 | Turing机、计算复杂性的概念、NP完全性理论及其应用 |
教材与参考书
- 《计算机算法设计与分析》（第2版），王晓东，电子工业出版社，2004
- Algorithm Design，Jon Kleinberg & Eva Tardos，清华大学出版社，2006
- Introduction to Algorithms，CLRS，McGraw-Hill，1998
- 《计算机和难解性——NP完全性理论导引》，Garey & Johnson，张立昂等译，科学出版社，1987
成绩评定
- 平时成绩：50%
- 期末笔试：50%
核心内容：引言
一、理论上的可计算 vs 现实上的可计算
- 理论上的可计算 → 可计算性理论（什么问题存在求解算法）
- 现实上的可计算 → 计算复杂性理论（算法需要多少时间/空间）
算法 + 数据结构 = 程序
二、五个经典算法问题
| # | 问题 | 输入 | 输出 |
|---|---|---|---|
| 1 | 投资问题 | m元钱，n个项目，效益函数f_i(x) | 分配方案使总效益最大 |
| 2 | Hanoi塔问题 | n个盘子，3根柱子 | 移动次数 T(n) = 2ⁿ - 1 |
| 3 | 搜索问题 | 数组L，数x | x是否在L中及其下标 |
| 4 | 排序问题 | n个数 | 按递增顺序排列的n个数 |
| 5 | 选择问题 | n个数集合S，正整数k | S中第k小的数 |
三、投资问题的蛮力分析
建模：max Σf_i(x_i)，s.t. Σx_i ≤ m
- 非负整数解 <x₁, x₂, …, x_n> 的个数：C(m+n-1, m) = Ω((1+ε)
- 结论：蛮力穷举代价太大，需要算法设计技术
- Stirling公式：n! = √(2πn) · (n/e)ⁿ · (1 + Θ(1/n))
四、Hanoi塔的启示
T(n) = 2T(n-1) + 1，T(1) = 1 → T(n) = 2ⁿ - 1
- 1秒移1个盘子，64个盘子需要约5000亿年
- 思考：是否存在更好的解法？（Hanoi塔已证明下界为2ⁿ-1）
- 变种：Reve难题（柱数增加）、奇偶盘号分别放置等
算法与算法分析基础
一、基本概念
问题：需要回答的一般性提问，通常含若干参数。
- 问题描述包含：对问题参数的一般性描述 + 解满足的条件
- 问题的实例：对问题参数的一组赋值
- 例：巡回售货员问题（TSP）——城市集合C + 距离函数d(c_i, c_j)，求最短哈密顿回路
算法：
- 非形式定义：有限条指令的集合，确定了解决某个问题的运算或操作序列
- 形式定义：对所有有效输入停机的Turing机
- 算法A解问题P：把P的任何实例作为A的输入，A能在有限步停机并输出正确解
二、算法的描述——伪码
- 类C/Pascal结构：赋值←、分支if-then-else、循环while/for/repeat-until、goto、调用、注释
- 允许使用自然语言
- 常忽略数据结构、模块、异常处理、变量说明等细节
插入排序算法是伪码示例（INSERTION-SORT）
三、算法的时间复杂度
| 类型 | 符号 | 定义 |
|---|---|---|
| 最坏情况 | W(n) | 输入规模为n的实例所需最长时间 |
| 平均情况 | A(n) | 输入规模为n的实例所需平均时间 |
顺序搜索的平均复杂度分析：
- 假设x在L中的概率为p，在L中不同位置等概分布
- W(n) = n
- A(n) = p(n+1)/2 + (1-p)n
四、复杂度函数的阶（渐近记号）
设f和g是定义域为自然数集N上的函数：
| 记号 | 名称 | 定义 | 直觉 |
|---|---|---|---|
| O(g(n)) | 上界 | ∃c, n₀ > 0，∀n≥n₀，0 ≤ f(n) ≤ c·g(n) | f增长”不快于”g |
| Ω(g(n)) | 下界 | ∃c, n₀ > 0，∀n≥n₀，0 ≤ c·g(n) ≤ f(n) | f增长”不慢于”g |
| Θ(g(n)) | 紧界 | f = O(g) 且 f = Ω(g) | f与g同阶 |
| o(g(n)) | 严格上界 | ∀c>0, ∃n₀, ∀n≥n₀, f(n) < c·g(n) | f比g低阶 |
| ω(g(n)) | 严格下界 | （对称定义） | f比g高阶 |
O(1) 表示常数函数
五、渐近阶的基本性质
- 极限判别法：若 lim(n→∞) f(n)/g(n) = c > 0，则 f(n) = Θ(g(n))
- 传递性：若 f = O(g) 且 g = O(h)，则 f = O(h)（Ω、Θ同理）
- 加法性质：若 f = O(h) 且 g = O(h)，则 f + g = O(h)
- 低阶吸收：若 g = O(f)，则 f + g = O(f)
六、基本函数类（阶从高到低）
指数级：2ⁿ, 3ⁿ, n!, ...
多项式级：n, n², n log n, n^(1/2), ...
对数多项式级：log n, log²n, ...
完整阶序列（从高到低）： 2ⁿ, n!, 2^(n/2), (3/2)ⁿ, (log n)^(log n) = Θ(n^(log log n)), n³, log(n!) = Θ(n log n), n = 2^(log n), log²n, log n, √log n, log log n, n^(1/log n) = Θ(1)
多项式时间 vs 指数时间
一、定义
- 多项式时间算法：时间复杂度为O(p(n))，其中p(n)是n的多项式
- 指数时间算法：不存在多项式p(n)使得时间复杂度为O(p(n))
二、时间增长速度对比
| 复杂度 | n=10 | n=20 | n=30 | n=40 | n=50 | n=60 |
|---|---|---|---|---|---|---|
| n | 10⁻⁵秒 | 2×10⁻⁵秒 | 3×10⁻⁵秒 | 4×10⁻⁵秒 | 5×10⁻⁵秒 | 6×10⁻⁵秒 |
| n² | 10⁻⁴秒 | 4×10⁻⁴秒 | 9×10⁻⁴秒 | 16×10⁻⁴秒 | 25×10⁻⁴秒 | 36×10⁻⁴秒 |
| n³ | 10⁻³秒 | 8×10⁻³秒 | 27×10⁻³秒 | 64×10⁻³秒 | 125×10⁻³秒 | 216×10⁻³秒 |
| n⁵ | 0.1秒 | 3.2秒 | 24.3秒 | 1.7分 | 5.2分 | 13.0分 |
| 2ⁿ | 0.001秒 | 1.0秒 | 17.9分 | 12.7天 | 35.7年 | 366世纪 |
| 3ⁿ | 0.059秒 | 58分 | 6.5年 | 3855世纪 | 2×10⁸世纪 | 1.3×10¹³世纪 |
三、计算机提速的效果
1小时可解的最大实例规模：
| 复杂度 | 当前计算机 | 快100倍 | 快1000倍 |
|---|---|---|---|
| n | N₁ | 100 N₁ | 1000 N₁ |
| n² | N₂ | 10 N₂ | 31.6 N₂ |
| n³ | N₃ | 4.64 N₃ | 10 N₃ |
| n⁵ | N₄ | 2.5 N₄ | 3.98 N₄ |
| 2ⁿ | N₅ | N₅ + 6.64 | N₅ + 9.97 |
| 3ⁿ | N₆ | N₆ + 4.19 | N₆ + 6.29 |
关键洞察：对于指数时间算法，计算机提速1000倍，能解决的问题规模仅增加约10（2ⁿ情况）或6（3ⁿ情况）。算法改进远比硬件提速有效。
问题复杂度分析
一、难解性
- 多项式时间可解问题P：存在解P的多项式时间算法
- 难解问题P：不存在解P的多项式时间算法
- 实际上可计算的问题 = 多项式时间可解的问题
二、复杂性类的层次结构
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME （大部分包含关系是否严格仍未证明）
核心问题：P = NP? —— 本世纪7个最重要的数学问题之一（千禧年大奖难题）
三、Turing奖中的算法与复杂性
- 1966-2005年Turing奖获奖50人
- 其中10人以算法设计获奖
- 7人以计算理论、自动机和复杂性研究获奖
拓展方向
算法领域
- 概率算法
- 在线算法
计算复杂性领域
- 概率Turing机与概率复杂性
- 近似解的复杂性
学习路线图
课程全景
├── 算法设计技术（6种）
│ ├── 分治策略
│ ├── 动态规划
│ ├── 贪心法
│ ├── 回溯算法
│ ├── 概率算法*
│ └── ...
├── 算法分析技术
│ ├── 评价标准
│ ├── 复杂度估计
│ ├── 问题下界
│ └── 分析实例
└── 计算复杂性理论
├── Turing机
├── 复杂性概念
└── NP完全性理论
关联笔记
- 《算法导论》-Introduction to Algorithms-第3版-CLRS — 参考教材之一，更完整的算法知识体系
- 《SICP》-计算机程序的构造和解释-第二版 — 计算机科学的另一基石课程
- 设计模式课程-第3讲-设计原则-王亚沙 — 另一门北大课程，面向对象设计原则
- 后续第2~10讲：分治/动态规划/贪心/回溯/NP完全性等