算法(4th ed)(169):基础——算法分析 6.5.3

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

算法(4th ed)(169):基础——算法分析 6.5.3

(设计更快的算法:下界)

表 1.4.8 总结了本节所讨论的内容。我们立即产生了一个有趣的疑问:我们还能找到比 2-sum 问题的 TwoSumFast 和 3-sum 问题的 ThreeSumFast 快得多的算法吗?是否存在解决 2-sum 问题的线性级别的算法,3-sum 问题的线性对数级别的算法?对于 2-sum,这个问题的回答是没有(成本模型仅允许使用并计算这些整数的线性或是平方级别的函数中的比较操作);对于 3-sum,回答是不知道,不过专家们相信 3-sum 可能的最优算法是平方级别的。为算法在最坏情况下的运行时间给出一个下界的思想是非常有意义的,我们会在 2.2 节中学习排序时再次讨论它。复杂的下界是很难找到的,但它非常有助于指引我们追求更加有效的算法。

算法(4th ed)(169):基础——算法分析 6.5.3

3-sum 问题的 N2lgN 解法

表 1.4.8 运行时间的总结

算法 运行时间的增长数量级
TwoSum N2
TwoSumFast NlogN
ThreeSum N3
ThreeSumFastN2logN

本节中所讨论的例子为我们学习本书中的其他算法打下了基础。在本书中,我们会按照以下方式解决各种新的问题。

  • 实现并分析该问题的一种简单的解法。我们通常将它们称为暴力算法,例如 ThreeSum 和 TwoSum。
  • 考查算法的各种改进,它们通常都能降低算法所需的运行时间的增长数量级,例如 TwoSumFast 和 ThreeSumFast。
  • 用实验证明新的算法更快。

在许多情况下,我们会学习解决同一个问题的多种算法,因为对于实际问题来说运行时间只是选择算法时所要考虑的各种因素之一。在本书中我们会在解决各种基础问题时逐渐理解这一点。

评论

发布