插入排序算法的大θ表示法

Question

我正在研究书中的渐近符号，我不明白作者的意思。我知道if f(n) = Θ(n^2) then f(n) = O(n^2)。然而，我从作者的话中了解到，对于插入排序函数算法f(n) = Θ(n)和f(n)=O(n^2)。

为什么？大欧米茄或大θ随输入的不同而变化吗？

他说：

但是，在插入排序的最坏情况下运行时间上的Θ(n^2)界并不意味着对每个输入的插入排序运行时间的Θ(n^2)绑定。

然而，它是不同的大-哦符号。他什么意思？他们之间有什么区别？

我真的很困惑。我把它贴在下面：

由于O-表示法描述了一个上界，当我们用它来定义算法最坏的运行时间时，我们对每个输入的算法的运行时间都有一个界。因此，插入排序在最坏情况下运行时间的O(n^2)界也适用于每个输入的运行时间。但是，在插入排序的最坏情况下，Θ(n^2)绑定并不意味着在每个输入上插入排序运行时间的Θ(n^2)绑定。例如，当输入已经排序时，插入排序将在Θ(n)时间内运行。

Answer 1

大欧米茄或大θ随输入的不同而变化吗？

是。为了给出一个简单的例子，考虑从左到右数组中的线性搜索。在最坏和平均情况下，对于某些常数a和b，该算法采用f(n) =a×n/2 +b期望步长，但当左元素始终保持所寻找的键时，它总是采取a+b步骤。

由于Θ表示严格的界，Θ(n) !=Θ(N 2)，因此这两种输入的Θ是不同的。

编辑：对于在相同的输入上不同的Θ和大O，是的，这是完全可能的。考虑下面的例子(无可否认是微不足道的)。

当我们把n设为5时，n=5和n<6都是真。但当我们将n设为1时，则n=5为假，而n<6仍为真。

类似地，大-O只是一个上界，就像< on数一样，而Θ是一个严格的界，例如=。

(实际上，Θ更像是常数a和b的

Answer 2

参考CLRS第3版第-44页(渐近表示法、函数和运行时间)，它说-

即使我们使用渐近表示法来应用于算法的运行时间，we need to understand which running time we mean。有时我们对worst-case运行时间感兴趣。Often, however, we wish to characterize the running time no matter what the input. In other words, we often wish to make a blanket statement that covers all inputs, not just the worst case.

从上述段落获得的款项：

• 最坏的情况为算法的运行时间提供了最高的限制。因此，插入排序在最坏情况下运行时间的O(n^2)界也适用于每个输入的运行时间。
• 但是，Theta(n^2)绑定在插入排序的最坏情况下的运行时间，但并不意味着Theta(n^2)绑定在每个输入的插入排序运行时间上。因为最好的情况下，插入排序的运行时间会产生Theta(n)。(当列表已经排序时)
• 我们通常编写一个算法的worst case时间复杂度，但当最佳情况和平均情况进入问责时，时间复杂度根据这些情况而变化。

Answer 3

简单地说，程序的运行时间被描述为输入大小的函数，即f(n)。

=是不对称的，因此an+b=O(n)表示f(n)属于集合O(g(n))。因此，我们也可以说an+b=O(n^2)及其真，因为f(n)对于a，b和n的某些值属于集合O(n^2)。

因此，大-哦(O)只给出一个上界，或者你可以说表示法给出了一个blanket statement，这意味着给定输入大小的所有输入都涵盖了，而不仅仅是最坏的情况。例如，在插入的情况下，对大小为n的数组进行反向排序。

因此，n=O(n^2)是正确的，但在为算法定义最坏的运行时间时将是一种滥用。最坏的情况是，运行时间为任何输入的运行时间提供了一个上限。我们都知道，在插入排序的情况下，运行时间将取决于输入在给定大小的数组中是如何排序的。因此，如果数组是排序的，则运行将是线性的。

因此，我们需要一个严格的渐近界表示法来描述我们的最坏情况，这是由Θ表示法提供的，因此插入排序的最坏情况是Θ(n^2)，最好的情况是Θ(n)。