第二章 算法效率分析基础

32
• MaxElement(A[0..n-1]) • //求给定数组中最大元素的值 • //输入：实数数组A[0..n-1] • //输出:A中最大元素的值 • maxval←A[0] 第二步： • for i←1 to n-1 do 找出算法基本操作： • if A[i]>maxval 比较？ • maxval←A[i] 赋值？ • return maxval
第二个符号Ω(g(n))，代表增长次数大于等于 g(n)(以及其常数倍,n趋向于无穷大)的函数集合。 n3∈ Ω(n2)， 1/2(n(n-1)) ∈ Ω(n2)， 但是100n+5 ∈/ Ω(n2)
16
最后，Θ(g(n))是增长次数等于g(n) (以及其常数 倍,n趋向于无穷大)的函数集合。 因些，每一个二次方程an2+bn+c在a>0的情况 下都包含在Θ(n2)中。
27
2.2.7基本的效率类型
O(1)< O(logn)< O(n)< O(nlogn)< O(n2)< O(n3) < O(2n)< O(n!)< O(nn) 常见的指数阶
1 log n n n log n n2 n3 2n n!
constant logarithmic linear n log n quadratic cubic exponential factorial
n0之前 的情况 无关重 要 ,为 什么？
n0
cg(n)
t(n)
常用函数符号： t(n) 一个算法运行的 时间函数 C(n)基本操作次数函 数 g(n) n 用来比较的函数
18
符号O：t(n)∈O(g(n))
• t(n)=3n+2。说明属于O(n) – 当n≥n0=2时，3n+2≤3n+n＝4n – 此时c=4, g(n)=n。（向定义式靠拢） – t(n) ≤4g(n) – t(n)∈O(n)
35
把C(n)记作比较运算的执行次数, 由于该算法每执行一次循环就会做一次比较， 并且对于循环变量i在1和n-1(包含在内)中的 每个值都会做一次循环，所以，我们得到 C(n)的下列求和表达式：
C ( n)
n 1 i 1
11
2.1.4 算法的最优、最差和平均效率
一个算法的最差效率是指当输入规模为n时，算 法的最坏情况下的效率。这时，相对于其他规 模为n的输入，该算法的运行时间最长。 为什么要考虑最坏效率？ 提供了对任何规模为n的实例，算法运行的上界 Cworst(n)
12
一个算法的最优效率是指当输入规模为n时，算法 在最优情况下的效率。这时，与其它规模为n的 输入相比，该算法运行得最快。
• 研究实验告诉我们，对于大多数问题来说，我们在速度 上能够取得的进展要远大于在空间上的进展，
• 所以我们把主要精力集中在时间效率上。
4
2.1 分析框架
如何评价时间效率？ 2.1.1 输入规模的度量
一个事实：问题规模越大，算法运行时间越长。 将算法输入规模n为时间效率的参数。 选择哪个（些）参数作为输入规模？
2 2
所以t(n) ∈ Ω(n2)。
22
2.2.4 符号Θ
定义 3 把函数t(n)包含在Θ(g(n)) 中，记作t(n) ∈ Θ(g(n)) ;
成立条件：对于所有足够大的n， t(n) 的上界和下界都由g(n) 的常数倍数所确定， 即，存在大于0的常数c1，c2和和非负的整数n0，使得：
对于所有的n≥ n0来说， c2g(n) ≤t(n) ≤ c1g(n)
长次数。
14
2.2 渐进符号和基本效率类型
2.2.1 非正式的介绍
非正式来说， O(g(n)) 是增长次数小于等于 g(n)(以及其常数倍，n趋向于无穷大)的函数集 合。
考虑O(n2) n∈O(n2), 100n+5∈O(n2), 1/2(n(n-1)) ∈O(n2), n3不属于O(n2),
15
斐波那契数列—0,1,1,2,3,5,8,13,21,34,…
观察特点是什么？ 从第3个数开始每一个数是前两个数之和。
如何写成递推式？： 当n>1时，F(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1
注意： 后面问题的n均从0开始。
1
算法1 F(n) //根据定义，递归计算第n个斐波那契数 //输入：一个非负整数n //输出：第n个斐波那契数 if n≤1 return n else return F(n-1)+F(n-2)
28
关于渐进时间效率：
当比较两个算法的效率时,若两个算法是同阶的,必 须进一步考察阶的常数因子才能辨别优劣。
29
2.1-2.2小结
30
2.3非递归算法的数学分析
如何用前面介绍的知识分析一个算法的效率
31
例1 考虑从n个元素的列表中查找元素最大值的问 题. 假设列表是用数组实现的。 MaxElement(A[0..n-1]) //求给定数组中最大元素的值 //输入：实数数组A[0..n-1] //输出:A中最大元素的值 第一步： 决定用哪个(哪些) maxval←A[0] 参数作为输入规模 for i←1 to n-1 do 的度量： if A[i]>maxval 数组元素的个数n maxval←A[i] return maxval
然而，无论是最差效率分析还是最优效率分析 都不能提供一种必要的信息：在“典型”或者 “随机”输入的情况下， 一个算法会具有什么 样的行为。这正是平均效率试图提供给我们信息。
13
2.1.5 分析框架概要
• 算法的时间效率和空间效率都用输入规模的函数进 行度量。 • 我们用算法基本操作的执行次数来度量算时间效率。 通过计算算法消耗的额外存储单元的数量来度量空 间效率。 • 在输入规模相同的情况下，有些算法的效率会的显 著差异。对于这样的算法，我们需要区分最差效率， 平均效率和最优效率。 • 本框架主要关心，当算法的输入规模趋向于无限大 的时候，其运行时间（消耗的额外空间）函数的增
17
2.2.2 符号О
定义1 把函数t(n)包含在O(g(n)) 中记作t(n) ∈ O(g(n))。 称 t(n) 的阶不高于g (n) 的阶. 成立条件：对于所有足够大的n， t(n) 的上界由g(n)的 常数倍数所确定。即，存在大于0的常数c和非负的 整数n0，使得：对于所有的n≥ n0来说， t(n) ≤c g(n)
19
• t(n)= 6 * 2n+ n2 。 – 可以观察到对于n≥n0=4，有n2 ≤2n – 所以对于n≥4，有t(n)≤6 * 2n+ 2n = 7 * 2n – g(n)= 2n – t(n) ≤7g(n) – t(n) ∈ O (2n )。
20
2.2.3 符号Ω
定义2 把函数t(n)包含在Ω(g(n))中，记作t(n)∈Ω(g(n)) 。称t(n) 的阶不低于g(n)的阶。 成立条件：对于所有足够大的n， t(n)的下界由g(n)的常数倍所 确定， 即，存在大于0的常数c和非负的整数n0，使得：
34
• MaxElement(A[0..n-1]) • //求给定数组中最大元素的值 • //输入：实数数组A[0..n-1] • //输出:A中最大元素的值 • maxval←A[0] 第四步： • for i←1 to n-1 do 建立一个算法基本操 • if A[i]>maxval 作执行次数的求和表 • maxval←A[i] 达式： • return maxval
对于所有的n≥ n0来说， t(n) ≥c g(n)
t(n) cg(n)
n0之前的情 况无关重要
n
n0
符号Ω：t(n)∈Ω(g(n))
21
存在大于0的常数c和非负的整数n0，使得： 对于所有的n≥ n0来说， t(n) ≥c g(n)
对于所有的n，有t(n) = 3n+ 2 > 3n，因此t(n) ∈ Ω(n)。 对于所有的n≥0，有t(n) = 10n + 4n+ 2 > 10n ，
2
第2章 算法效率分析基础
• 一个问题往往有多个算法 • 应当分析算法的品性
–怎样评价一个算法？
3
• 一个算法好不好体现在运行该算法所需要的计算机资源 的多少上
–所需资源越少，该算法越好；
• 计算机最重要的资源是
–时间和空间
• 算法分析对算法利用这两种资源的效率做研究 • 时间效率：指出正在讨论的算法运行得有多快； • 空间效率：关心算法需要的额外空间。
基本操作的 执行时间
基本操作次数
7
• 对下面的三个时间效率函数表达式,哪一个效率 高? • C1(n)=n • C2(n)=n3 结论： n • C3(n)= 10 1 随n的递增，不同函数增幅 不同 • n=1 2 某些函数在大规模时增幅显 • 1 1 10 著，函数可以表示增幅的特点 • n=2 3 我们希望选择大规模时，时 • 2 8 100 间效率增幅小的算法 • n=3 • 3 27 1000 • n=非常大 8
• 2.1.3增长次数（增长幅度）
• 特别考虑大规模的输入要强调执行次数的增长 次数呢？这是因为小规模输入在运行时间上差别 不足以将高效的算法和低效的算法法区分开来。
9
•
• C(n)可以合理的度量算法的效率，但对同一个算 法相同的规模下运行时间就一样吗？ • 考虑顺序查找： • SequentialSearch(A[0..n-1],K) • //输入：数组A[0..n-1],和查找关键字K • //输出：返回第一个匹配K的元素下标 • //如果没有匹配的，返回-1 • i=0 同为n时： • While i<n and A[i]<>K do 什么是最坏情况 • i=i+1 什么是最好情况 • If i<n return i • Else return -1