算法与计算复杂性课程(8)算法分析

《算法与计算复杂性课程(8)算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、顺序算法分析的基本方法算法分析的原则正确性、工作量、占用空间简单性、最优性（问题复杂度）算法分析的实例搜索有序表排序选择1算法分析的原则正确性概念在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的.正确性证明的内容：方法的正确性证明——算法思路的正确性.证明一系列与算法的工作对象有关的引理、定理以及公式.程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作.程序正确性证明的方法：大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块,分别验证.小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等2工作量--时

2、间复杂性分析计量工作量的标准:对于给定问题,该算法所执行的基本运算的次数.基本运算的选择：根据问题选择适当的基本运算问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针两种时间复杂性:最坏情况下的复杂性W(n)平均情况下的复杂性A(n)3占用空间--空间复杂性分析两种占用:存储程序和输入数据的空间存储中间结果或操作单元所占用空间--额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小如果额外空间相对于输入规模是常数,称为原地工作的算法.两种空间复杂性:最坏情况下的

3、复杂性和平均情况下的复杂性.4简单性含义：算法简单，程序结构简单.好处：容易验证正确性便于程序调试简单的算法效率不一定高.要在保证一定效率的前提下力求得到简单的算法.5最优性含义指求解某类问题中效率最高的算法两种最优性最坏情况下最优：设A是解某个问题的算法,如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低,则称A是解这个问题在最坏情况下的最优算法.平均情况下最优：设A是解某个问题的算法,如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低,则称A是解这个问题在平均情况下的最优算

4、法.6寻找最优算法的途径设计算法A,求W(n).相当于给出最坏情况下的一个上界.寻找函数F(n),使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算.相当于对问题给出最坏情况下所需基本运算次数的一个下界.如果W(n)=F(n),则A是最优的.如果W(n)>F(n),A不是最优的或者F(n)的下界过低.改进A或设计新算法A’使得W’(n)F(n).重复以上两步,最终得到W’(n)=F’(n)为止.7例1在n个不同的数中找最大的数基本运算:比较算法findmax输入数组L,项数

5、n≥1输出L中的最大项MAX1.MAX←L(1);i←2;2.whilei≤ndo3.ifMAX

6、法–一片树叶代表一个输入–从根到某片树叶的路径代表算法对这个输入的工作量–树深代表最坏情况的工作量，平均路径长度代表平均工作量•算法类的最坏情况下时间复杂度下界：所有的树中深度最浅的树的树深.•算法类的平均情况下时间复杂度下界：所有的树中平均深度最浅的树的树深.10下界证明法二：构造最坏输入任意给定一个算法A，A对于任意输入x都存在一个确定的操作序列τ•τ中的操作分成两类：–决定性的：能够对确定输出结果提供有效信息–非决定性的：对确定结果没有帮助的冗余操作•根据算法A构造某个输入实例x，使得A对x的操作序列τ包含尽量多的非决定性操作.•给出冗余操作+必要的操作

7、的计数公式11下界证明法三：归约条件•已知问题Q最坏情况下时间复杂度下界为F(n)，即求解Q的任何算法A最坏情况的时间≥F(n)•需要确定问题P的算法类最坏情况下的时间复杂度下界方法•设计一个求解Q的算法A，A调用任意解P的算法B.时间为T(n)=t(n)+p(n)+t(n)：t为把Q的实例I转换到P的A121实例f(I)的时间，t为把P的解s转换成Q的解的时间2•若t(n),t(n)=O(p(n))，

8、f(I)

9、=O(n)，则T(n)=Θ(p(n))12Ap(n)=Θ(T(n))=Ω(F(n))A结论P至少与Q一样难12算法分析的实例搜索有序表顺序搜索、改进

10、顺序搜索、二分搜索最优性的分析排序起泡