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

Question

已知插入排序的最佳情况运行次为n，最坏情况运行次为n²。在那种情况下，它的θ值大吗？

Answer 1

简而言之，是的。 Big-Theta 始终存在。问题是：你说的是最好情况、最坏情况还是平均情况？ 和 你能证明吗？

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

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

案例与界限

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

• 案例：最好的情况，最坏的情况，平均的情况
• 界限： 上限 (O)、下限 (Ω)、确切界限 (Θ)

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

然后当你分析那个案例时，你可以尝试确定它的上限和下限。

宽松界限

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

• 建立 Ω(1) 的下界很简单。我的意思是，每个算法都有一个恒定的下限。它并不总是 紧 下限，但它是 a 下限。
• 类似地，可以从 O(n!) 的非常宽松的上限开始。如果您只是简单地迭代输入列表的每个排列，直到 运行 跨越一个排序的列表，这就是需要多长时间。这是世界上最糟糕的排序算法。插入排序肯定比那表现得更好，对吧？

紧边界

下限和上限为算法在 best/worst/average 情况下的表现设定了下限和上限。但是，如果它们太松散，它们就没那么有用了。越紧越好。

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

等边界

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

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

如果我们能够证明插入排序在最坏情况下的性能最好是Ω(n²)，最坏情况下是O(n²) 然后我们知道它是 正好 Θ(n²).

多个 Θ

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

如果你这样做，你最终会得到三个答案。三个 Big-Thetas。

• 最佳情况： Θ(n)
• 最坏情况： Θ(n²)
• 平均情况： Θ(n²)

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