第一周1.5问题的下界.pdf

《第一周1.5问题的下界.pdf》由会员分享，可在线阅读，更多相关《第一周1.5问题的下界.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

05 问 题 的 下 界 32 问题的下界(Lower Bounds)，即任何一种算法解决 一个问题所必需的最小运行时间。 假定一个问题的下界为F(n) ，而当前解决该问题的 最好的算法为A，其最坏情形时间复杂度为W(n)， 如果F(n) = W(n) ，则A是最优算法 。 五、问题的下界 33 找最大元素 FindMax() 1 max2 2 for j2 to n do 3 if Ajmax then 4 maxAj 5 return max 下界 n-1 最坏情形时间复杂度 n-1 五、问题的下界 34 程序是用某种程序设计语言实现的算法，而算法是抽象的， 它不依赖于具体的程序设计语言和硬件。 Turing奖获得者，Pascal语言之父Niklaus Wirth曾说过 “程序=数据结构+算法”。 Turing奖获得者，算法大师Donald E. Knuth说过计算机科 学的研究就是算法的研究。 52名Turing奖（类似诺贝尔奖）的获得者中，因为算法方 面的贡献而获奖的就有30多个。 分析一个算法的运行时间应该主要关注与问题规模有关的 主要项，其他低阶项，甚至主要项的常数系数都可以忽略。 小结 谢 谢 大 家