算法-第2章-算法效率分析基础(李静).ppt

练习 P40 8T 答案 思考题 P47 Problem 10 P52 Problem 4 2.6 算法的经验分析 目的 检验算法效率理论结论的精确性 比较相同问题的不同算法或者相同算法的不同实现间的效率 方法 在算法的程序实现中插入一些计数器为基本操作计数 记录待讨论算法程序实现的运行时间 2.7 算法可视法 使用图形来传达关于算法的一些有用信息 算法对于不同输入的性能 算法的执行速度与求解相同问题的其他算法的比较 变种 静态算法可视法 动态算法可视法，也称算法动画(sorting out sorting on /programs/view/5_iTRpSF5KY/) 第二章习题讲解 P42/8T. 证明本节定理对于下列符号也成立 a.Ω符号 b.Θ符号 证明： a.we need to proof that if t1(n)∈Ω(g1(n)) and t2(n)∈Ω(g2(n)), then t1(n)+ t2(n)∈Ω(max{g1(n), g2(n)})。 由 t1(n)∈Ω(g1(n))， t1(n)≥c1g1(n) for all n=n1, where c10 由 t2(n)∈Ω(g2(n))， T2(n)≥c2g2(n) for all n=n2, where c20 那么，取c=min{c1,c2},当n=max{n1,n2}时： t1(n)+ t2(n)≥c1g1(n)+ c2g2(n) ≥c g1(n)+c g2(n)≥c[g1(n)+ g2(n)]≥cmax{ g1(n), g2(n)} 所以以命题成立。 b. t1(n)+t2(n) ∈Θ( 证明：由大?的定义知，必须确定常数c1、c2和n0，使得对于所有n=n0，有： 由t1(n)∈Θ(g1(n))知，存在非负整数a1,a2和n1使： a1*g1(n)=t1(n)=a2*g1(n)-----(1) 由t2(n)∈Θ(g2(n))知，存在非负整数b1,b2和n2使： b1*g2(n)=t2(n)=b2*g2(n)-----(2) (1)+(2): a1*g1(n)+ b1*g2(n)=t1(n)+t2(n) = a2*g1(n)+ b2*g2(n) 令c1=min(a1,b1),c2=max(a2,b2)，则 C1*(g1+g2)= t1(n)+t2(n) =c2(g1+g2)-----(3) 不失一般性假设max(g1(n),g2(n))=g1(n). 显然，g1(n)+g2(n)2g1(n)，即g1+g22max(g1,g2) 又g2(n)0，g1(n)+g2(n)g1(n),即g1+g2max(g1,g2)。 则（3）式转换为： C1*max(g1,g2) = t1(n)+t2(n) =c2*2max(g1,g2) 所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n=n0时上述不等式成立。 证毕。 P52/6T a. 判断输入矩阵是否为对称矩阵。若是对称矩阵，则返回“true”,否则返回“false”. b. 基本操作为比较： P58 解下列递推关系 a. 当n1时, 解： b. 当n1时 解： P59/7T. 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。 建立该算法所做的加法运算次数的递推关系并求解 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 对于该问题的求解来说，这是一个好的算法吗？ a.算法power(n) //基于公式2n=2n-1+2n-1,计算2n //输入:非负整数n //输出: 2n的值 If n=0 return 1 Else return power(n-1)+ power(n-1) c. 6. 考虑下面的算法 该算法求的是什么？ 它的基本操作时什么？ 该基本操作执行了多少次？ 该算法的效率类型是什么？ 对该算法进行改进，或者设计一个更好的算法，然后指出他们的效率类型。如果你做不到这一点，请试着证明这是不可能做到的。 e. 算法无改进版本。因为在最坏情况下，比较次数必须为 n*(n-1)/2次。 2.3 非递归算法的数学分析 例1 ：考虑一下从n个元素的列表中查找元素最大值的问题. 简单起见,我们假设列表是用数组实现的。下面给出一个 解决问题的标准算法的伪代码。 算法 MaxElement(A[0..n-1]) //求给定数组中最大元素的值 //输入：实