算法(4th ed)(172):基础——算法分析 6.6.2

阅读数:4 2019 年 11 月 9 日 15:02

算法(4th ed)(172):基础——算法分析 6.6.2

(倍率实验:评估使用更快的计算机所产生的价值)

你可能会面对的另一个基本问题是:“如果我能够得到一台更快的计算机,解决问题的速度能够加快多少?”一般来说,如果新计算机比老的快 x 倍,运行时间也将变为原来的 x 分之一。但你一般都会用新计算机来处理更大规模的问题,这将会如何影响所需的运行时间呢?同样,增长的数量级信息也正是你回答这个问题所需要的。

著名的摩尔定律告诉我们,18 个月后计算机的速度和内存容量都会翻一番,5 年后计算机的速度和内存容量都会变为现在的 10 倍。表 1.4.9 说明如果你使用的是平方或者立方级别的算法,摩尔定律就不适用了。进行倍率测试并检查随着输入规模的倍增前后运行时间之比是趋向于 2 而非 4 或者 8 即可验证这种情况。

表 1.4.9 根据增长的数量级函数作出的预测

运行时间的增长数量级系数为 2系数为 10处理输入规模为 N 的数据需要若干小时的某个程序
描述函数处理 10N 的预计时间在快 10 倍的计算机上处理 10N 的预计时间
线性级别N210一天几个小时
线性对数级别NlogN210一天几个小时
平方级别N24100几个星期一天
立方级别N381000几个月几个星期
指数级别2N2N29N永远永远

评论

发布