插入排序有 ?(n) 值吗？

Question

众所周知，插入排序的最佳情况运行时间为n，最坏情况运行时间为n ²。在这种情况下，它是否具有很大的 theta 值？

Answer 1

简短的回答，是的，确实如此。Big-Theta 始终存在。问题是：你是在谈论最好的情况、最坏的情况还是平均情况？并且你能证明这一点？

最佳情况和最坏情况与 Big-O 或 Big-Theta 不同。最好的情况是有一个 Big-Theta。最坏的情况有不同的 Big-Theta。他们不一样。

让我解释一下我所做的区分。

案例与界限

进行复杂性分析的人通常对他们的符号非常松懈。这是一个很好的问题，需要精确。Case 和 bound 是不同的、正交的概念。重要的是不要将它们混为一谈。

• 案例：最好的情况，最坏的情况，平均情况
• 界限：上限（O），下限（？），精确界限（？）

每个案例都有自己的界限。当您分析算法的复杂性时，您需要首先确定您正在分析的情况。您是否正在寻找最佳案例性能？最坏的情况？平均情况？

然后，当您分析该案例时，您可以尝试确定其上限和下限。

松散的界限

重要的是要认识到没有单一的上限或下限。其中有很多。例如，让我们看看插入排序在最坏情况下的性能。它有很多下界，也有很多上界。

• 建立 ?(1) 的下界很简单。我的意思是，每个算法都有一个恒定的下界。它并不总是一个严格的下限，但它是一个下限。
• 同样，可以从一个非常松散的 O(n!) 上界开始。如果您简单地迭代输入列表的每个排列直到遇到一个排序的排列，这就是需要多长时间。这是世界上最糟糕的排序算法。当然插入排序的性能比那更好，对吧？

严格的界限

下限和上限为算法在最佳/最差/平均情况下的表现设置了下限和上限。不过，如果它们太松，它们就没那么有用了。你可以把它们做得越紧越好。

• ?(n) 将是比 ?(1) 更严格的下限。并且很容易证明？（1）：排序算法当然必须检查输入列表的每个元素，这需要线性时间。如果我们证明了这一点，那么我们就知道插入排序的最坏情况性能不仅是?(1)，还是?(n)。
• 正如您所说，众所周知，最坏情况下的性能上限为 O(n ² )。这是一个比 O(n!) 更严格的上限。

等界

如果您能够证明下限和上限相同，那么您将得到一个精确的界限，?。大西塔。为此，您需要将上限和下限挤在一起，直到它们在准确的正确答案上相遇。

• 我们知道 O(n ² ) 是可能的最严格的上限。
• 为了得到 ?，那么，我们需要将下界收紧到 ?(n ² )。证明这不是这个答案的真正重点，所以让我们假设我们已经这样做了。

如果我们能够证明插入排序的最坏情况性能最好是 ?(n ² )，最坏情况是 O(n ² )，那么我们就知道它正是?(n ² )。

多个?s

我上面写的所有内容都是针对最坏情况的性能。如果您想查看最佳案例性能或平均案例，您必须为这些再次重复所有分析。您必须建立自己的上限和下限并收紧它们直到它们相等。

如果你这样做了，你最终会得到三个答案。三个大Theta。

• 最好的情况： ?(n)
• 最坏情况： ?(n ² )
• 平均情况： ?(n ² )

事实上，你甚至可以想出更多的 Big-Theta。最好、最坏和平均情况并不是唯一可以分析的情况。它们是最常见的，当然，但我可以想象其他有自己的下限和上限的。