算法(4th ed)(179):基础——算法分析 6.7.6

阅读数:7 2019 年 11 月 9 日 15:38

算法(4th ed)(179):基础——算法分析 6.7.6

(注意事项:对输入的强烈依赖)

在研究程序的运行时间的增长数量级时,我们首先作出的几个假设之一就是运行时间应该和输入相对无关。当这个条件无法满足时,我们很可能无法得到一致的结果或是验证我们的猜想。例如,假设我们为回答:“输入中是否存在和为 0 的三个整数?”而修改 ThreeSum 并返回 boolean 值,将 cnt++ 替换为 return true 并在最后加上 return false 作为结尾,那么如果输入中的头三个整数的和为 0,该程序的运行时间的增长数量级为常数级别;如果输入不含有这样的三个整数,程序的运行时间的增长数量级则为立方级别。

评论

发布