算法分析基础和数学预备知识
第1章 算法分析基础和数学预备知识
提纲
算法及特征 计算复杂性 最好情况,最坏情况和平均情况 数学预备知识 证明方法 递推关系 数据结构
1
算法及特征
算法(Algorithm):通俗地讲,算法是解决问题的方 法,严格地说,算法是对特定问题求解步骤的一种描述, 是指令的有限序列。
执 行 次 数
n情0
之 况
前 无
的 关
紧要
n0 大Ω符号的含义
f(n) c×g(n)
可以看做一个下界
问题规模n
7
Θ符号(很少使用)
定义 令f(n)和g(n)是两个函数,如果存在一个自然数n0和两个正常数 c1,c2,对于任意n≥n0,都有c1 g(n) ≤ f(n) ≤c2g(n),则称f(n)= Θ(g(n))
执 行 次 数
n情0
之 况
前 无
的 关
紧要
n0 Θ符号的含义
c1×gn) f(n) c2×g(n)
算法在运行时间上 有确切界限
问题规模n
推论 f(n)=Θ(g(n)),当且仅当f(n)= O(g(n))并且f(n)= Ω(g(n))
例 T(n)=3n-1 当n≥1时,3n-1≤3n=O(n) 当n≥1时,3n-1≥3n-n=2n=Ω(n) 当n≥1时,3n≥3n-1≥2n,则3n-1=Θ(n)
例 T(n)=5n2+8n+1 当n≥1时,5n2+8n+1≤5n2+8n+n=5n2+9n≤5n2+9n2≤14n2=O(n2) 当n≥1时,5n2+8n+1≥5n2=Ω(n2) 当n≥1时,14n2≥5n2+8n+1≥5n2,则5n2+8n+1=Θ(n2)
8
提纲
算法及特征 计算复杂性 最好情况,最坏情况和平均情况 数学预备知识 证明方法 递推关系 数据结构
9
最好情况: 很少关注最好情况
最坏情况: 非常重要,给出一个上界
平均情况: 算法要处理不同的输入
n: 输入规模; m: 不同输入的组数 pi: 第i组输入的概率 ti : 算法计算第i组数据的时间
m
A(n) = ∑ pi*ti i=1
∑ A(n) = 1
m
ti
m i=1
等概率情况
提纲
算法及特征 计算复杂性 最好情况,最坏情况和平均情况 数学预备知识 证明方法 递推关系 数据结构
x≡y(mod n):x和y被n除的时候,余数相同。称为:x和y模n同余
• 对数
log2x写作log x • 底函数⎣x⎦和 顶函数⎡x⎤
• 阶乘和二项式系数
-
二项式系数:n选k,⎜⎛ ⎝
n k
⎞ ⎟ ⎠
=
C
n k
=
n! k !(n −
,n k )!
≥
k
≥
0
- 重要等式:
(1)
⎛ ⎝⎜
n k
⎞ ⎠⎟
辗转相除法的伪代码描述 1. Read m, n; 2. 循环直到 n=0 2.1 r=m % n; 2.2 m=n; 2.3 n=r; 3. 输出 m;
4
算法设计的一般过程
理解问题
预测所有可能的输入
确定: z精确解还是近似解 z确定数据结构 z算法设计技术
设计并描述算法
跟踪算法
分析算法的效率
满意
j =1
6
∑ ∑ (3) 几何级数
n c j = cn+1 −1 = Θ(cn ), c ≠ 1; n 2 j = 2n+1 −1 = Θ(2n );
j =1
c −1
j =1
∑ ∑ n
j =1
1 2j
=2−
1 2n
< 2 = Θ(1);
n j =1
j 2j
= 2−
n+2 2n
= Θ(1)
12
提纲
算法及特征 计算复杂性 最好情况,最坏情况和平均情况 数学预备知识 证明方法 递推关系 数据结构
求两个正整数 a 和 b 的最大公约数(辗转相除法): 1. a ÷ b,令r为所得余数(0≤r<b) 若 r = 0,算法结束;b 即为答案。 2. 互换:置 a←b,b←r, 并返回第一步。
2
⑵ 流程图
优点是直观易懂,缺点是 严密性不如程序设计语言
输入a, b r←mod(a,b)
a ←b b ←r
求解递递归方程的技术
(1) 猜测技术 (2) 扩展递归技术 (3) 通用分治递推式
15
(1) 猜测技术 例:
T
(n)
=
⎧ ⎩⎨2T
(n
1 / 2)
+
n
n=2 n>2
假定T(n)≤n2,证明这个猜测的正确性。
为了计算方便,假定n=2k 证明: 当n=2时,T(2)=1 ≤22 设n=2k时,T(n)满足猜测,即
T(2k) ≤(2k)2 当n=2k+1时,从递归方程可得 T(2k+1)=2T(2k)+2k+1 ,代入上式有 2T(2k)+2k+1 ≤2(2k)2 +2*2k ≤4(2k)2 ≤(2k+1)2 由此, T(n) ≤n2成立, T(n) =O(n2) 用类似的方法可以证明:T(n) ≤nlog2n
提纲
算法及特征 计算复杂性 最好情况,最坏情况和平均情况 数学预备知识 证明方法 递推关系 数据结构
19
• 线性结构 线性表,栈,队列,存储结构,插入,删除,… …
•图 Graph G=<V, E>,生成树、完全图、路、回路、哈密顿 回路,… …
• 树和二叉 深度、高度、层数、节点数,… …
证明方法
算法的正确性以及算法的计算复杂度,很多都可以 通过预设断言的证明来确立
直接证明 要证明P→Q,先假设P为真,然后从P为真推出Q为真 例:如果n是偶数,则n2也是偶数。
间接证明 P→Q逻辑等价于 ¬Q→¬P 例如:证明如果n2是偶数,那么n是偶数 ⇔如果n是奇数,那么n2是奇数
反证法证明:假设结果不成立,推出一个矛盾。 反例证明:证明算法不总是带有一定性质的结果 数学归纳法证明
应用:
T
(n)
=
⎧ ⎩⎨2T
(n
1 / 2)
+
n
n=2 n>2
a=2, b=2, c=1, k=1
因a=bk, T (n) = O(n log2 n)
18
算法的后验分析
算法的后验分析(Posterior)也称算法的实验分 析,通常需要将算法转换为对应的程序并上机运行。
原因:有的算法很难用数学计算分析,特别是做 平均情况分析的时候
例 令G=(V, E)是一个连通的无向图,有m个顶点,令p是G中访问n>m个
顶点的一条路径,那么p必定包含一条回路。
证明:存在一个顶点,必定至少访问过⎡n/m⎤次
• 和式
一些重要的和式:
(1) 算术级数
∑n j = n(n +1) = Θ(n2 )
j =1
2
(2) 平方和
∑nቤተ መጻሕፍቲ ባይዱj2 = n(n +1)(2N +1) = Θ(n3)
由T(2)=1可得 T ( 2k )= 2k-1 + 2k + 2k + … + 2k ≤k* 2k
以n代替2k,便得 T (n) = O(n log2 n)
(3)通用分治递推式
T
(n)
=
⎧ ⎩⎨aT
(n
/
c b)
+
cnk
n =1 n >1
其中 a≥1,表示分解后需要求解的子问题个数 b>1,n/b表示自子问题的规模 c是常数,表示解1规模问题的时间 cnk,表示合并各个子问题的解需要的时间
根据算法编写代码
不满意
提纲
算法及特征 计算复杂性 最好情况,最坏情况和平均情况 数学预备知识 证明方法 递推关系 数据结构
5
计算复杂性
对算法有效性的度量:时间和空间,即当给出合法输 入时,为了得到输出,该算法所需要的时间和空间
200
180
x2/8
160
3*x−2
140
x+10
10
数学预备知识
集合 关系
- 令A和B是两个集合,A和B的笛卡儿积是所有有序对(a, b)的集 合,其中a∈A, b ∈ B,笛卡儿积记为A×B,即
A×B={(a, b)| a ∈ A且b ∈ B}, R⊆ A×B 称R为从A到B的一个二元关系
- 偏序、等价关系 - 例如:R={(x, y)|x, y是整数,且x≡y(mod n)},
F r=0 T 输出a
⑶ 程序设计语言
优点是可由计算机直接执行。 缺点是抽象性差,描述算法的具体细节,很难观察算法的 整体逻辑。
3
⑷ 伪代码 伪代码(Pseudocode)是介于自然语言和程序设计语言之 间的方法,它采用某一程序设计语言的基本语法,操作指 令可以结合自然语言来设计。 伪代码不是一种实际的编程语言,但在表达能力上类似于 编程语言,同时极小化了程序语言中的技术细节,是比较 合适的描述算法的方法,被称为“算法语言”
=
⎛ ⎝⎜
n n
−
k
⎞ ⎟⎠
∑ ∑ (2)(1+ x)n =
j
n =0
⎛ ⎜ ⎝
n j
⎞ ⎟x ⎠
j
,
若x
=
1,
那么
2n =
n ⎛n⎞
⎜ j=0 ⎝
j
⎟ ⎠
11
鸽巢原理