算法设计与分析 - 第1讲：课程介绍与算法基础
基本信息
- 课程名称：算法分析与设计 (Design and Analysis of Algorithms)
- 课号：0A002
- 授课教师：屈婉玲 (qwll@pku.edu.cn)
- 来源：田浩然上传的资料/0A002算法分析与设计/lecture1.pdf
课程目标
- 掌握组合算法设计的基本技术
- 掌握算法分析的基本方法
- 了解计算复杂性理论的基本概念及其应用
课程内容结构
一、顺序算法设计的基本技术
- 分治策略
- 动态规划
- 回溯算法
- 贪心法
- 概率算法*
二、顺序算法分析的基本方法
- 评价算法的标准
- 算法复杂性的估计
- 问题复杂性的下界
- 算法分析的实例
三、计算复杂性理论的基本概念
- 计算复杂性的概念
- Turing机
- NP完全性理论及其应用
教材与参考书
- 《计算机算法设计与分析》（第2版），王晓东，电子工业出版社，2004.7
- Algorithm Design，Jon Kleinberg, Eva Tardos，清华大学出版社，2006
- Introduction to Algorithms，Thomas H. Cormen等，McGraw-Hill Book Company, 1998 (2000)
- 《计算机和难解性》——NP完全性理论导引，M. R. 加里, D. S. 约翰逊，张立昂等译，科学出版社，1987
学习安排
- 以课上讲授为主
- 成绩评定：平时成绩50%，期末笔试50%
核心概念：算法的设计与分析
算法 + 数据结构 = 编程
好的算法能够：
- 提高求解问题的效率
- 节省存储空间
研究层次
| 层次 | 内容 |
|---|---|
| 问题 → 寻找求解算法 | 算法设计技术 |
| 算法 → 算法的评价 | 算法分析技术 |
| 算法类 → 问题复杂度的评价 | 问题复杂性分析 |
| 问题类 → 能够求解的边界 | 计算复杂性理论 |
计算的性质
理论上的可计算 —— 可计算性理论
研究目标：确定什么问题是可计算的，即存在求解算法。
合理的计算模型条件：
- 计算一个函数只要有有限条指令
- 每条指令可以由模型中的有限个计算步骤完成
- 指令执行的过程是确定的
Church-Turing论题：如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的。
关键结论：可计算性是不依赖于计算模型的客观性质。
现实上的可计算 —— 计算复杂性理论
研究内容：
- 算法复杂度 —— 算法所使用的时间、空间的估计
- 问题复杂度 —— 估计问题的难度
术语和概念：
- 问题：需要回答的一般性提问，通常含有若干参数
- 算法：有限条指令的集合，指今集确定了解决某个问题的运算或操作的序列
算法的复杂度分析
时间复杂度
最坏情况下的时间复杂度：算法求解输入规模为n的实例所需要的最长时间 W(n)
平均情况下的时间复杂度：算法求解输入规模为n的实例所需要的平均时间 A(n)
复杂度函数的阶
大O记号：f(n) = O(g(n))
- 若存在正数 c 和 n₀ 使得对一切 n ≥ n₀ 有 0 ≤ f(n) ≤ cg(n)
大Ω记号：f(n) = Ω(g(n))
- 若存在正数 c 和 n₀ 使得对一切 n ≥ n₀ 有 0 ≤ cg(n) ≤ f(n)
Θ记号：f(n) = Θ(g(n))
- f(n) = O(g(n)) 且 f(n) = Ω(g(n))
小o记号：f(n) = o(g(n))
- 对所有正数 c < 1，存在 n₀ 使得对一切 n ≥ n₀ 有 0 ≤ f(n) < cg(n)
基本函数类（按阶的高低）
| 阶的类型 | 示例 |
|---|---|
| 指数级 | 2ⁿ, 3ⁿ, n!, … |
| 多项式级 | n², n log n, n^(1/2), … |
| 对数多项式级 | log n, log²n, … |
重要关系：
- 2^(log n) = n
- n! = Θ((n/e)^n * sqrt(2πn))
- log(n!) = Θ(n log n)
- n^(1/log n) = Θ(1)
多项式时间与指数时间
多项式时间的算法
时间复杂度函数为 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¹³世纪 |
问题与算法的定义
问题
需要回答的一般性提问，通常含有若干参数。包含：
- 对问题参数的一般性描述
- 解满足的条件
实例：对问题的参数的一组赋值。
算法
- 非形式定义：有限条指令的集合
- 形式定义：对所有的有效输入停机的 Turing 机
算法求解问题 P
把问题 P 的任何实例作为算法的输入，算法能够在有限步停机，并输出该实例的正确解。
算法的描述 —— 伪码
保持程序的主要结构：
- 赋值语句：←
- 分支语句：if …then …[else…]
- 循环语句：while, for, repeat …until
- 转向语句：goto
- 调用
- 注释：//*…
允许使用自然语言，常忽略数据结构、模块、异常处理等细节。
插入排序伪码
算法 INSERTION-SORT(A)
1. for j ← 2 to length[A]
2. do key ← A[j]
//*将A[j]插入排好序的序列 A[1..j–1]
3. i ← j–1
4. while i > 0 and A[i] > key
5. do A[i+1] ← A[i]
6. i ← i –1
7. A[i+1] ← key
计算的分类
| 类别 | 说明 |
|---|---|
| P类问题 | 存在解P的多项式时间的算法 |
| 难解的问题 | 不存在解P的多项式时间的算法 |
| 实际上可计算的问题 | 多项式时间可解的问题 |
复杂性类的谱系
不同复杂性类之间存在层次结构，从简单的P类到更复杂的NP、PSPACE等。
计算复杂性理论的拓广方向
- 算法方向：概率算法、在线算法
- 计算复杂性方向：概率Turing机与概率复杂性、近似解的复杂性
核心问题
“P = NP?” 是本世纪7个最重要的数学问题之一（1996-2005期间，Turing奖获奖50人，其中10人以算法设计获奖）。
关联笔记：