算法分析与设计之算法分析.pps

第二章算法分析的原则和实例
算法分析的原则
正确性
工作量
占用空间
简单性
最优性
一、正确性
定义:在给定有效输入后, 算法经过有限时间的计
算并产生正确的答案, 就称算法是正确的.
正确性证明的内容:
方法的正确性证明——算法思路的正确性.
证明一系列与算法的工作对象有关的引理、定
理以及公式.
程序的正确性证明——证明所给出的一系列指令
确实做了所要求的工作.
程序正确性证明的方法:
大型程序的正确性证明——可以将它分解为小的
相互独立的互不相交的模块, 分别验证.
小模块程序可以使用以下方法验证:
数学归纳法、软件形式方法等
二、工作量--时间复杂性分析
计量工作量的标准: 对于给定问题,该算法所执行
的基本运算的次数.
基本运算的选择:根据问题选择适当的基本运算
问题基本运算
在表中查找x 比较
实矩阵相乘实数乘法
排序比较
遍历二叉树置指针
两种时间复杂性:
最坏情况下的复杂性W(n)
平均情况下的复杂性A(n)
三、占用空间--空间复杂性分析
两种占用:
存储程序和输入数据的空间
存储中间结果或操作单元所占用空间--额外空间
影响空间的主要因素:
存储程序的空间一般是常数(和输入规模无关)
输入数据空间为输入规模O(n)
空间复杂性考虑的是额外空间的大小
如果额外空间相对于输入规模是常数, 称为原地
工作的算法.
两种空间复杂性:
最坏情况下的复杂性和平均情况下的复杂性.
四、简单性
含义:算法简单,程序结构简单.
好处:容易验证正确性
便于程序调试
简单的算法效率不一定高. 要在保证一定效率的前提下力求得到简单的算法.
五、最优性
1. 含义:指求解某类问题中效率最高的算法
2. 两种最优性
最坏情况下最优:设A是解某个问题的算法, 如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低, 则称A是解这个问题在最坏情况下的最优算法.
平均情况下最优:设A是解某个问题的算法, 如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低, 则称A是解这个问题在平均情况下的最优算法.
3. 寻找最优算法的途径(以最坏情况下的最优性为例)
(1) 设计算法A,求W(n).
相当于对问题给出最坏情况下的一个上界.
(2) 寻找函数F(n),使得对任何算法都存在一个规模为n
的输入并且该算法在这个输入下至少要做F(n)次基
本运算.
相当于对问题给出最坏情况下所需基本运算次数的
一个下界.
(3) 如果W(n)=F(n),则A是最优的.
(4) 如果W(n)>F(n),A不是最优的或者F(n)的下界过低.
改进A或设计新算法A’使得W’(n)<W(n).
重新证明新下界F’(n)使得F’(n)>F(n).
重复以上两步,最终得到W’(n) = F’(n)为止.
例1 问题: 在n个不同的数中找最大的数
基本运算: 比较
算法 findmax
输入数组L, 项数 n1 1
输出 L中的最大项MAX
1. MAXL(1); i2;
2. while in do
3. if MAX<L(i) then MAXL(i);
4. ii+1;
end.
行3的比较进行n-1次, 故W(n) = n-1.
定理
在n个数的数组中找最大的数, 并以比较作为基本运算的算法类中的任何算法最坏情况下至少要做n-1次比较.
证因为MAX是唯一的, 其它的n-1个数必须在比较后被淘汰. 一次比较至多淘汰一个数, 所以至少需要n-1次比较.
结论: findmax算法是最优算法.
算法分析的实例
一、搜索有序表
顺序搜索改进的顺序搜索
二分搜索最优性的分析
二、排序
起泡排序快速排序与归并排序
堆排序最优性的分析
三、选择
选择最大选最大和最小
选第二大选中位数
最优性分析