PKU算法分析与设计课程讲义
主讲： 屈婉玲 (qwl@pku.edu.cn) 课程代号： 0A002 教材： 计算机算法设计与分析（第2版），王晓东，电子工业出版社，2004.7
一、课程概述
目的
- 掌握组合算法设计的基本技术
- 掌握算法分析的基本方法
- 了解计算复杂性理论的基本概念及其应用
内容
| 模块 | 重点 |
|---|---|
| 顺序算法设计技术 | 分治、动态规划、回朔、贪心、概率算法 |
| 顺序算法分析 | 复杂度估计、问题复杂度下界 |
| 计算复杂性理论 | Turing机、NP完全性理论 |
主要公式
- Algorithm + Data Structure = Programming
- Stirling公式：
- 投资问题：，,
二、算法基础
算法定义
非形式定义：有限条指令的集合，每条指令由有限个计算步骤完成。 形式定义：对所有有效输入停机的Turing机。
算法 = machine
伪码描述
保持程序主要结构，类C/Pascal风格：
Algorithm INSERTION-SORT(A):
for j = 2 to length[A]
key = A[j]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
算法复杂度
- 最坏情况： - 输入规模为时的最长时间
- 平均情况： - 输入规模为时的平均时间
- 复杂度表示：将基本运算次数表示为输入规模的函数
三、计算复杂性理论
基本分类
| 复杂度类 | 说明 | 算法类型 |
|---|---|---|
| 线性 | 搜索问题（顺序搜索） | |
| 平方 | 插入排序 | |
| 立方 | - | |
| 指数 | TSP等难解问题 | |
| 指数 | 更难解问题 |
定义
- ：存在，使得对所有有
- ：存在，使得对所有有
- ：且
计算复杂性谱系
P (多项式时间可解)
|
v
BPP, ZPP, ...
|
v
NP (非确定多项式)
|
v
NP-hard / NP-complete (难解问题)
著名公式
- Church-Turing论题：如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的
- P=NP?：本世纪7个最重要的数学问题之一
四、经典问题与算法
Hanoi塔问题
, → 64个盘子需要5000亿年
5个基本问题
- 投资问题 - 多项目投资收益最大化（整数规划）
- Hanoi塔 - 递归结构，
- 搜索问题 - 数组中查找元素
- 排序问题 - 按递增顺序排列
- 选择问题 - 找到第k小的数
五、复杂度分析示例
示例：PrimalityTest(n)
1. s = n
2. for j = 2 to s
3. if j divides n then return false
5. return true
时间复杂度：（假设乘法） 不能写成，因为复杂度可能不同
示例：
证明：取
六、NP完全性理论
核心结论
- P类：存在多项式时间算法的问题
- NP类：解的存在性可在多项式时间内验证的问题
- NP-hard / NP-complete：难解问题类
复杂性类谱系
- P / NP / co-NP / PSPACE / EXPTIME
- 近似算法、概率算法、在线算法、并行算法
课程资源
- 教学网站：ftp.ss.pku.edu.cn
- 成绩评定：平时50% + 期末笔试50%