oiy*_*yio 5 algorithm complexity-theory big-o insertion-sort
我正在研究书中的渐近符号，但我无法理解作者的意思。我知道if f(n) = \xce\x98(n^2) then f(n) = O(n^2)。然而，我从作者的话中了解到，对于插入排序函数算法f(n) = \xce\x98(n)和f(n)=O(n^2).
为什么？大欧米茄或大西塔会随着不同的输入而改变吗？
\n\n他说：
\n\n\n\n\n然而，插入排序最坏情况运行时间上的 \xce\x98(n^2) 界限并不意味着每个输入上插入排序的运行时间上都有 \xce\x98(n^2) 界限。 ”
\n
然而，对于大哦表示法来说，情况有所不同。他什么意思？它们之间有什么区别？
\n\n我很困惑。我将其复制粘贴到下面：
\n\n\n\n由于 O 表示法描述了一个上限，因此当我们使用它来限制算法的最坏情况运行时间时，我们对每个输入的算法运行时间都有一个限制。因此，O(n ^2) 插入排序最坏情况运行时间的限制也适用于每个输入的运行时间。然而，\xce\x98(n^2) 对插入排序最坏情况运行时间的限制，\n 并不意味着 \xce\x98(n^2) 对每个输入的插入排序运行时间的限制.\n 例如，当输入已排序时，插入排序会在\n \xce\x98(n) 时间内运行。
\n
\n\n\n大欧米茄或大西塔会随着不同的输入而变化吗？
\n
是的。举一个更简单的例子，考虑在数组中从左到右的线性搜索。在最坏和平均的情况下，该算法对某些常数a和b采取 f( n ) = a \xc3\x97 n /2 + b预期步骤。但是，当保证左侧元素始终持有您要查找的密钥时，它总是需要a + b步骤。
\n\n由于 \xce\x98 表示严格界限，且 \xce\x98( n ) != \xce\x98( n \xc2\xb2) ，因此两种输入的 \xce\x98 是不同的。
\n\n编辑：至于 \xce\x98 和 big-O 在同一输入上不同，是的，这是完全可能的。考虑以下（诚然微不足道的）示例。
\n\n当我们将n设置为 5 时，则n = 5 和n < 6 均成立。但是当我们将n设置为 1 时，n = 5 为假，而n < 6 仍然为真。
\n\n类似地，big-O 只是一个上限，就像数字上的 < 一样，而 \xce\x98 是一个严格的界限，就像 = 一样。
\n\n（实际上， \xce\x98 更像是常量a和b的a < n < b，即它定义了类似于数字范围的东西，但原理是相同的。）
\n