算法分析与设计第3章

1、 每节一经典用系统的观点观察问题总体设计，逐步求精算法设计7部曲问题定义问题分析数学模型计算模型-算法设计算法分析算法优化重复操作是复杂算法的重要特征，解决办法有：循环结构，递归结构。（1）循环结构设计要注重效率（时间、空间）问题：例如，求1/1!-1/3!+1/5！-1/7!+(-1)n+1/(2n-1)!分析:此问题需要先进行累乘（求阶乘）,再把累乘的结果的符号倒数进行累加.数学建模：Sn=Sn-1+(-1)n+1/(2n-1)!计算机建模（计算模型）：S=S+(-1)n+1/(2n-1)!，(这个式子称为循环不变式).算法设计1: 2重循环实现，效率低。第3讲 算法工具与优化技巧Main

2、()int i,n,j,sign=1; float s,t=1; input(n); s=1; for(i=2;i=n;i=i+1) t=1; for(j=1;j=2*i-1;j=j+1) t=t*j; sign=1; for(j=1;j=i+1;j=j+1) sign=sign*(-1); s=s+sign/t; print(“sum”,s); 算法分析：1)算法正确。因为算法能实现解决问题的目标。2)算法可终止。当输入确定的n值后，内、外循环的 次数都是有限的，其他语句各执行一次，语句个数也是有限的，所以算法执行有限次后必然终止。3）算法时间复杂度是O(n2).缺陷：算法效率低O(n2)。

3、原因:(1)每一个数的阶乘都需要计算：1*2*3*m, (2)每一次循环需要重复计算sign=sign*(-1)， 共n*(n-1)/2次，这是没有必要的。改进：从数学模型入手 Sn=Sn-1+(-1)n+1An ; An=An-1*1/(2*n-2)*(2*n-1).计算模型： S=S+(-1)n+1/A; A=A*(2*i-2)*(2*i-1); 再优化： (-1)n+1用sign=-sign实现。循环不变式: S=S+(-1)n+1/(2n-1)!Main()int i,n,j,sign=1; float s,t=1; input(n); s=1; sign=1; for(i=2;i0)

4、 hanoi(n-1,a,c,b) move(a,b) hanoi(n-1,c,b,a); 第3讲 算法工具与优化技巧定理 3.1 对n阶汉诺塔问题，共需2n-1次移动操作. 证明：用数学归纳法。1）当n=1时，只需要移动一个盘子到目标基座，需要1次操作，即21-1=1，此时结论成立。2）当n=2时，只需要移动3次，即可把2个盘子移到目标基座,可表示为： 2*(21-1)+1=2*2-2+1=22-1=3，此时结论成立。3）假设n=k时，结论成立（k1），即k阶汉诺塔问题，共需2k-1次移动操作.4) 当n=k+1时，把k个盘子看成一个整体（看成一个盘子），再把第k+1个盘子和 k个盘子构成的

5、那个整体盘子一起看作2个盘子进行移动。由2)知，共需要移 动次数：2*(2k-1)+1= 2k+1-1. 综合1）、2）、3）、4），定理得证。因此，上述算法的时间复杂度是：O(2n), 即指数复杂度的，也就是说它是NP问题。 第3讲 算法工具与优化技巧小结：循环算法效率问题：尽可能降低循环嵌套，提高时间效率。递归算法设计要点,步骤。练习：1)试用手工操作，画出4或5阶汉诺塔求解过程。 2）设计汉诺塔求解算法，如有兴趣可在机器上运行 ，看看当n增大时，算法所用时间长短变化情况。 3）预习：P61-68,递归与循环比较 第3讲 算法工具与优化技巧Thats all for todaySee yo

6、u next timeGood bye! 递归与循环比较递归是实现“重复操作”的一种机制，通过把大问题化小，小问题化到能解问题为止，再由小到大把问题的解“累积”起来，从而得到最大问题（原问题）的解，需要用到数据结构中的栈（stack）来暂时存贮中间结果。重要结论：定理3.2 每个迭代算法原则上总可以转换成与其功能等价的递归算法；反之不然，即并不是每个递归算法都可以转换成与其功能等价的迭代算法。证明：提示：后一部分结论证明只需举例汉诺塔问题作为反例即可证明。前半部分结论需要程序变换知识，比较难（省略，有兴趣的同学可以试一试）。注意： 有些递归程序转化为非递归程序需要栈(stack)辅助，有些则不

7、需要栈(stack)辅助。第3讲 算法工具与优化技巧递归与循环比较递归算法优缺点： 优点： 1）更接近自然语言理解 2）算法简洁，设计难度小 3）正确性容易证明 4）复杂性容易分析缺点： 1）时间效率低（执行速度慢：保存中间结果现场、返回时回收资源 需要时间） 2）空间效率低（用stack保存中间结果现场）第3讲 算法工具与优化技巧递归与循环比较迭代算法优缺点： 缺点： 1）不接近自然语言，难理解 2）有些算法较长 3）有些算法正确性不容易证明 4）有些算法复杂性不容易分析 5）适用范围小，设计难度大优点： 1）时间效率高（一般不需要保存中间结果现） 2）空间效率高（一般不用stack保存中间结果现场）第3讲 算法工具与优化技巧例7,8例10从n个自然数中取r个数的组合.n=5,r=35 4 35 4 25 4 15 3 25 3 15 2 1算法与数据结构（自己复习、看书总结） 算法+数据=程序 数据=数据元素+存贮结构所以存贮结构影响算法，算法影响存贮结构。作业：p75, 例15；p77,例17第3讲 算法工具与优化技巧算法优化技巧（自己复习、看书总结）