我正在研究书中的渐近符号，我无法理解作者的意思。我知道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) 时间内运行。
大欧米茄或大θ会随着不同的输入而变化吗？
是的。举一个更简单的例子，考虑从左到右的数组中的线性搜索。在最坏和平均的情况下，该算法对某些常数a和b采取 f( n ) = a × n /2 + b预期步骤。但是，当保证左元素始终持有您要查找的键时，它总是需要a + b步骤。
由于 Θ 表示严格界限，并且 Θ( n ) != Θ( n ²)，因此两种输入的 Θ 是不同的。
编辑：至于 Θ 和 big-O 在同一输入上不同，是的，这是完全可能的。考虑以下（诚然微不足道的）示例。
当我们将n设置为 5 时，n = 5 和n < 6 都为真。但是当我们将n设置为 1 时，n = 5 为假，而n < 6 仍然为真。
类似地，big-O 只是一个上限，就像数字上的 < 一样，而 Θ 是一个严格的边界，例如 =。
（实际上，对于常数a和b， Θ 更像a < 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算法的时间复杂度，但是当考虑到最佳情况和平均情况时，时间复杂度会根据这些情况而变化。
简而言之，程序的运行时间被描述为其输入大小的函数，即 f(n)。
是不对称的=，因此 an+b=O(n) 意味着 f(n) 属于集合 O(g(n))。所以我们也可以说 an+b=O(n^2) 并且它是真的，因为 f(n) 对于 a,b 和 n 的某些值属于集合 O(n^2)。
因此 Big-Oh(O) 只给出一个上限，或者您可以说符号给出 a blanket statement，这意味着给定输入大小的所有输入都被覆盖，而不仅仅是最坏情况一次。例如，在插入排序的情况下，以相反的顺序对大小为 n 的数组进行排序。
所以 n=O(n^2) 是正确的，但在定义算法的最坏情况运行时间时会被滥用。作为最坏情况，运行时间给出了任何输入的运行时间上限。众所周知，在插入排序的情况下，运行时间将取决于输入在固定大小的给定数组中的排序程度。因此，如果数组是排序的，则运行将是线性的。
所以我们需要一个严格的渐近界表示法来描述我们的最坏情况，这是由 Θ 表示法提供的，因此插入排序的最坏情况是 Θ(n^2)，最好情况是 Θ(n)。
我们对每个输入的算法运行时间都有一个限制
这意味着如果有一组输入具有运行时间n^2而其他的运行时间较少，那么算法是O(n^2)。
然而，对插入排序的最坏情况运行时间的 Θ(n^2) 限制并不意味着对每个输入的插入排序的运行时间有一个 Θ(n^2) 限制
他是说反之亦然。如果算法是O(n^2)，这并不意味着每个输入都将以二次时间运行。
我对插入排序算法的学术理论在过去很遥远，但从我对您的复制粘贴的理解来看：
big-O 表示法总是描述最坏的情况，但 big-Theta 描述的是典型数据的某种平均值。
看看这个：Θ（n）和O（n）有什么区别？