插入排序算法的Big Theta符号
我正在研究书中的渐近符号，我不明白作者的意思。 我知道if f(n) = Θ(n^2) then f(n) = O(n^2) 。 然而，从作者的话我明白，对于插入排序函数算法f(n) = Θ(n)和f(n)=O(n^2) 。
为什么？ 大欧米茄或大欧塔会因不同的输入而改变吗？
他说：
“然而，在插入排序的最坏情况运行时间上限制的Θ（n ^ 2）并不意味着在每个输入上插入排序的运行时间上限制了Θ（n ^ 2）。”
然而，它与大哦表示法不同。 他什么意思？ 他们有什么区别？
我很困惑。 我把它粘贴在下面：
由于O-notation描述了一个上界，当我们用它来限制算法的最坏情况运行时间时，我们在每个输入上对算法的运行时间都有约束。 因此，在插入排序的最坏情况运行时间上限制的O（n ^ 2）也适用于其在每个输入上的运行时间。 然而，在插入排序的最坏情况运行时间上限制的Θ（n ^ 2）并不意味着在每个输入上的插入排序的运行时间上限制了Θ（n ^ 2）。 例如，当输入已经排序时，插入排序以Θ（n）时间运行。
大欧米茄或大欧塔会因不同的输入而改变吗？
是。 举一个更简单的例子，考虑从左到右的数组中的线性搜索。 在最差和平均情况下，该算法对某些常数a和b采用f（n）= a×n / 2 + b预期步长。 但是，当左边的元素总是保持你要找的键时，它总是需要+ b的步骤。
由于Θ表示严格的界限，并且Θ（n）！=Θ（n 2），因此两种输入的Θ是不同的。
编辑 ：至于Θ和大O在相同的输入是不同的，是的，这是完全可能的。 考虑以下（无可否认）的例子。
当我们将n设置为5时，那么n = 5和n <6都是真的。 但是当我们将n设置为1时，那么当n <6时，n = 5是假的。
同样，big-O只是一个上限，就像<on数字，而Θ是一个严格的边界，如=。
（实际上，对于常量a和b，Θ更像是一个<n <b，即它定义了类似于数字范围的东西，但原理相同。）
请参阅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时间复杂度，但是当最佳情况和平均情况出现问责时，时间复杂度会根据这些情况而变化。
我们对每个输入的算法运行时间都有约束
这意味着如果有一组运行时间为n^2的输入，而其他运行时间较少，则算法为O(n^2) 。
但是，在插入排序的最坏情况运行时间上限制的Θ（n ^ 2）并不意味着在每个输入上的插入排序的运行时间上限制了Θ（n ^ 2）
他在说，相反是不正确的。 如果算法是O(n^2) ，它并不意味着每一个输入都会以二次方式运行。