算法设计与分析 03算法分析.ppt

算法设计与分析
——问题下界的分析方法
2018/7/2
1
算法设计与分析演示稿纪玉波制作(C)
前面已讲过,对于一个问题来说,所有能解决此问题的算法中最快的算法的复杂性,叫做这个问题的复杂性。所以问题的复杂性就是此问题所有算法的复杂性的下界(lower bound),即不会有此问题的算法比下界Tl再快了。凡是一个算法的运算时间等于该问题的Tl,此算法叫做最优的算法。
算法的运算时间不仅和问题的规模n有关,往往还与具体输入的数据有关。一般在考虑运算时间时可有两种考虑办法:一种办法是考虑平均情况,即考虑同样n值时各种可能的输入,取它们运算时间的平均值;另一种办法是考虑最坏情况,即考虑各种可能的输入中运算最慢的一种情况。考虑平均情况时算法的复杂性称为平均复杂性,考虑最坏情况时算法的复杂性称为最坏复杂性。一般情况下总是考虑最坏的情况,所以不特别说明时,算法的复杂性是指最坏情况时的复杂性。研究问题的下界,也是指最坏的输入情况。
2018/7/2
2
问题下界的分析方法
所谓问题的下界,是指某一规模n的问题在输入数据不利的情况下至少需要多少运算次数。知道了问题的下界,可以对一个算法进行评价看是否最优。下面介绍两种分析问题下界的方法
2018/7/2
3
1. 信息论下界
有很多问题,靠一系列的回答提问即可解决,且每个提问只有“是”或“否”两种答案。例如对集合{x1,…,xn}进行排序的问题,只要回答一系列的“是否xi<xj”即可解决。对这类问题,可以构成一个二分树,树中每个非终端节点代表一次提问,每个终端节点则表示一个可能的结果。如下图所示。
2018/7/2
4
2018/7/2
5
如果在最不利的情况下需要提问的次数为h,则树的高度为(h+1),终端节点数目最多不会超过2h。设此问题可能的结果共有M种,显然:
M≤2h 或 h≥logM (以2为底对数)
因h必然是整数,故
这就是信息论下界。所需要的提问次数在输入数据最不利的情况下不会低于此值。
2018/7/2
6
下面举一个按此方法分析下界的例子:
例1. 对集合{x1,…,xn}进行排序,此问题在不同的输入数据下可能的结果数共有M=n!种,故按信息论下界,在最不利情况下所需要的比较次数。
下图所示为随x的变化曲线,其中带阴影部分的面积等于logi。
2018/7/2
7
2018/7/2
8
为推导简单,近似取:
则
2018/7/2
9
当n较大时O(n)一项可以忽略不计,由此可知此排序问题的下界Tl=nlongn。排序问题中的合并排序算法其比较次数即为nlongn,所以合并排序是最优的排序算法之一。
应说明并非各种问题都可用此方法求下界,下面两个例子即不可用上述方法来求。
2018/7/2
10