Jor*_*edo 4 algorithm time-complexity
我一直在努力理解Best Conceivable Runtime 和 Best Case Runtime之间的区别。两者之间你怎么看？Best Case Runtime 是最佳运行时吗？如果是这样，人们如何决定最佳时间？
在最好的情况下运行时意味着你必须解决该问题，并在最好的情况下，该算法有一个特定的时间复杂度的算法。
例如，选择排序的最佳运行时间是 O(n 2 )，因为无论数组是什么，它总是会执行那么多操作。另一方面，在输入数组已经排序的情况下，插入排序的最佳运行时间是 O(n)。
在最好的可能的运行时介绍，据我所知，在这本书的一个概念破解编码面试由盖尔·麦克道尔Laakmann。这意味着您遇到了问题，并且您正在尝试估计解决问题的效率；您还没有算法，或者如果您有算法，那么您不知道是否有另一种算法可能具有较低的渐进时间。
可以想象的最佳运行时间意味着这是您可以想象问题可能得到解决的最佳时间，而且绝对不可能比这更快地解决问题。这是一个快速检查你排除其中某些方法不可能工作，因为如果他们没有工作，他们会得太快。
例如，排序问题无法在 O(n) 平均时间下解决，因为仅执行正确的写入/交换以将元素放在正确的位置就需要 O(n) 时间。这并不意味着存在一种以 O(n) 平均时间排序的算法，只是平均而言绝对不可能比 O(n)做得更好。
一个更好的论据可以表明，基于比较的排序算法的最佳运行时间平均为 O(n log n)，因为每次比较仅提供有关输入数组所在排列的一位信息，因此您至少需要记录2 (n!) 次比较以区分所有 n! 可能的排列。因此，不可能编写一个基于比较的排序算法，该算法在数组上使用单个循环，并且每次迭代都执行 O(1) 工作；在尝试设计算法时，我们可以排除这种可能性。在这种情况下，是分拣符合这个渐近界算法基于比较的，所以它的紧。
因此，在某种程度上，对于给定的问题，并没有真正的“最佳运行时间”，这取决于您证明给定运行时间是解决问题的所有可能算法的下限的能力。