最佳想象运行时间与最佳情况运行时间之间的区别

Question

最佳想象运行时间与最佳情况运行时间之间的区别

algorithmtime-complexity

6

我一直很难理解 最佳可行运行时间和最佳情况运行时间 之间的区别。您认为这两者之间有什么区别？最佳情况运行时间是最优运行时间吗？如果是，那么如何确定最佳可行时间？

- Joross Barredo

1

你为什么认为它们是不同的？我从未听说过最佳可想象运行时间，在缺乏更多信息的情况下，我会认为这与最佳情况运行时间相同。 - Patrick87

@Patrick87 抱歉信息不足。这个术语来自Gayle Laakmann McDowell的《Cracking the Coding Interview》一书。 - Joross Barredo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kaya3 · Accepted Answer

最佳情况下的运行时间指您拥有解决问题的算法，并且在最佳情况下，该算法具有特定的时间复杂度。

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

据我所知，最佳可行运行时间是Gayle Laakmann McDowell在书中提出的一个概念《Cracking the Coding Interview》。它意味着你有一个问题，并且正在尝试估计解决问题的效率；你还没有算法，或者如果你已经有了算法，那么你不知道是否有另一个算法可能具有更低的渐进时间。

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

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

更好的论证可以表明，基于比较的排序算法的最佳可行运行时间在平均情况下为O(n log n)，因为每个比较仅提供输入数组所在排列的一位信息，因此您需要至少进行log₂(n!)次比较才能区分所有n！种可能的排列。因此，在尝试设计算法时，我们可以排除在数组上使用单个循环并每次迭代执行O(1)工作的可能性。在这种情况下，存在满足这个渐进界限的基于比较的排序算法，因此它是紧密的。

因此，在某种程度上，对于给定问题实际上没有一个"最佳可行运行时间"，它取决于你证明一个给定运行时间是解决问题的所有可能算法的下界的能力。