algorithm - 最佳可想象运行时与最佳案例运行时之间的区别

Question

我一直在努力理解 之间的区别最佳设想运行时和最佳案例运行时 .两者之间你怎么看？ Best Case Runtime 是最佳运行时吗？如果是这样，人们如何决定最佳时间？

Answer 1

最佳案例运行时间 意味着您有一个解决问题的算法，并且在最好的情况下，该算法具有特定的时间复杂度。

例如，选择排序的最佳运行时间是 O(n2)，因为无论数组是什么，它都会执行那么多操作。另一方面，在输入数组已经排序的情况下，插入排序的最佳运行时间是 O(n)。

最佳运行时间 是一个概念介绍，据我所知，在书Cracking the Coding Interview盖尔·拉克曼·麦克道威尔。这意味着您遇到了问题，并且您正在尝试估计解决问题的效率；您还没有算法，或者如果您有算法，那么您不知道是否有另一种算法可能具有较低的渐进时间。

可以想象的最佳运行时间意味着这是您可以想象问题可能得到解决的最佳时间，而且绝对不可能比这更快地解决问题。这是一个快速检查，您可以排除某些可能行不通的方法，因为如果它们确实有效，它们将太快。

例如，排序问题无法在 O(n) 平均时间下解决，因为仅执行正确的写入/交换以将元素放在正确的位置就需要 O(n) 时间。这并不意味着存在以 O(n) 平均时间排序的算法，只是它是 绝对不可能做得更好平均比 O(n)。

更好的论据可以表明 comparison-based sorting 的最佳运行时间算法平均是 O(n log n)，因为每次比较只给出关于输入数组在哪个排列中的一位信息，所以你需要 at least log₂ (n!) comparisons区分所有n!可能的排列。因此，不可能编写使用 a single loop 的基于比较的排序算法。在数组上，每次迭代执行 O(1) 工作；我们可以在尝试设计算法时排除这种可能性。在这种情况下，有基于比较的排序算法满足这个渐近边界，所以它很紧。

因此，在某种程度上，对于给定的问题，并没有真正的“最佳运行时间”，这取决于您证明给定运行时间是解决问题的所有可能算法的下限的能力。