Algorithms Chapter 2 算法效率分析基础.pptVIP

* * * * * * * * 算法可视法 通过使用图形来传达关于算法的一些有用信息。 算法可视法的种类： 静态算法可视法 动态算法可视法(算法动画, Algorithm Animation) * 静态算法可视法 * 静态算法可视法 * 动态算法可视法 2000年，当第一次公开恋情，王菲31岁，谢霆锋20岁，王菲的年龄是谢霆锋的1.55倍。转眼到了2014年，如今两人破镜重圆，王菲45岁，谢霆锋34岁，王菲的年龄是谢霆锋的1.32倍。1）求两人年龄倍数与公历年的时间序列收敛函数，收敛域以及收敛半径。2）这件事给张柏芝和李亚鹏留下了巨大的心理阴影，求阴影面积是多少？3）如果用挖掘机填补阴影面积，那么，请问，挖掘机技术哪家强？ * 解：1. 根据可惜准则：设f(x，y)在a≤x+∞，c≤y≤d 上连续，对于任意给定的y，∫(a → +∞)f(x，y)dx收敛。若对于任意给定的正实数ε，都存在一个只与ε有关与y无关的正整数A0，对于任意的AA0，c≤y≤d 均有|∫(A → +∞) f(x，y)dx|ε，则称含参变量的无穷积分∫(a → +∞)f(x，y)dx在c≤y≤d 上一致收敛。如果王和谢一直和好到终老100岁，即王的值域为55，谢的值域为66，取两者交集为55，年龄倍数为a, 王/谢的年龄比从1.55 → 1.32, ∫(a → 1)f(x，y)dx在45≤y≤100 上一致收敛,即张和谢年龄倍数和公里年序列在收敛域是[45,100]是收敛函数, 收敛域是[45,100],收敛半径为[1,1.55] 2. 根据量子力学波动方程，设张柏芝受伤时间为E，张心理阴影形成时间为P 因为E=?ω，p=h/λ， ?=h/2π 得到ΔxΔp≥?/2=h/4π 由波方程解出张心理阴影面积每秒 , h=6.626176pin 设定面积为F.2 得，张心理阴影面积部分为F.2=6.626176平方米， 即张每秒钟心理产生阴影6.626176平方米，而解答1中得出的收敛于上限为 另，根据爱因斯坦狭义相对论原理， ，经过洛伦兹变换后： * 即，设李心理受伤时间为T，相对论因子γ可根据张和李相对的空间求得：张在香港，李在新疆，两地空间绝对距离3384千米，时差7200秒，因此γ= 1.001 根据上式，解出T= 2.56t,就是说，张每伤心一秒，李就要伤心2.56秒，因此，李每秒受伤的心理面积F.（2）= 16.9631平方米。 3. 要用挖掘机挖土方来填埋受伤体积为V，单位面积为S，张和李的平均身高为h,h=1.78m 即V= S.h=(6.626t + 16.9631t)* 1.78 = 41.99t,这就说张和李每秒钟产生的心理阴影体积有42立方米。工程量巨大，这对挖掘机选手技术要求很高，请到山东找蓝翔！ * * 小结 算法效率包括时间效率和空间效率。 时间效率主要用它的输入规模的函数来度量，该函数计算算法基本操作的执行次数。 最差、最优与平均效率 增长次数 符号O，Ω，Θ 非递归算法和递归算法的效率分析 递归算法简洁性可能会掩盖它的低效率 算法的经验分析是针对一个输入样本，运行算法的一个程序实现，然后分析观测到的数据。 作业 1.按增长率由小至大的顺序排列下列各函数： 2100, (2/3)n，(3/2)n， nn , n! ，2n ，lgn ,nlgn, n(3/2) * * * * * * * * * * * * * * * * * * * * * * * Hong YU The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms Hong YU The Design and Analysis of Computer Algorithms Hong YU The Design and Analysis of Computer Algorithms Hong YU The Design and Analysis of Computer Algorithms 算法分析与设计 算法效率分析基