算法(4th ed)(176):基础——算法分析 6.7.3

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

算法(4th ed)(176):基础——算法分析 6.7.3

(注意事项:指令时间)

每条指令执行所需的时间总是相同的假设并不总是正确的。例如,大多数现代计算机系统都会使用缓存技术来组织内存,在这种情况下访问大数组中的若干个并不相邻的元素所需的时间可能很长。如果让 DoublingRatio 运行的时间长一些,你可能可以观察到缓存对 ThreeSum 所产生的效果。在运行时间的比例看似收敛到 8 以后,由于缓存,对于大数组该比例也可能突然变为很大的值。

评论

发布