仍然有点混淆Big O符号

Question

所以我一直试图尽可能地理解Big O符号,但仍有一些我很困惑的事情.所以我一直在读,如果有东西是O(n),它通常指的是算法的最坏情况,但它不一定要参考最坏的情况,这就是为什么我们可以说最好的例如,插入排序的大小是O(n).但是,我无法理解这意味着什么.我知道如果最坏情况是O(n ^ 2),这意味着在最坏情况下表示算法的函数增长不快于n ^ 2(存在上限).但如果你有O(n)作为最好的情况,我应该怎么读呢？在最好的情况下,算法增长不比n快？我的图片是以n为上限的图形,如

如果算法的最佳情况是O(n),那么n是算法运算在最佳情况下增长的速度的上限,因此它们不能比n增长得快......但这并不意味着它们可以像O(log n)或O(1)那样快速增长,因为它们低于上限？这没有意义,因为O(log n)或O(1)是比O(n)更好的场景,所以O(n)不是最好的情况吗？我很失落哈哈

Answer 1

Big-O,Big-Θ,Big-Ω独立于最坏情况,平均情况和最佳情况.

符号f(n)= O(g(n))意味着f(n)的增长不会比g(n)的某个常数倍增长.
符号f(n)=Ω(g(n))意味着f(n)的增长速度不比g(n)的某个常数倍慢.
符号f(n)=Θ(g(n))表示以上两者均为真.

注意,这里的f(n)可以表示输入大小为n的程序的最佳情况,最坏情况或"平均"运行时间.
此外,"平均"可以有很多含义:它可以表示平均输入或平均输入大小("预期"时间),或者它可以表示长期(摊销时间),或两者,或其他.

通常,人们感兴趣的是最坏的情况下运行的程序的时候,摊销整个程序的运行时间(所以如果有什么成本ň最初但成本只有1次,下一次ñ元素,它平均到的成本每个元素2).这里衡量的最有用的是最坏情况下的最小上限 ; 所以,通常情况下,当你看到有人要求程序的Big-O时,这就是他们正在寻找的东西.

类似地,为了证明问题本质上是困难的,人们可能试图表明最坏情况(或可能是平均情况)的运行时间至少是一定量(例如,指数).
你会为这些使用Big-Ω表示法,因为你正在寻找这些的下限.

但是,最坏情况和Big-O,或者最佳情况和Big-Ω之间没有特殊关系.
两者都可以用于其中之一,只是其中一个比另一个更典型.

因此,上限最好的情况并不是非常有用.是的,如果算法总是花费O(n)时间,那么你可以说它是最好的情况下的O(n),以及平均值,以及最坏的情况.这是一个非常好的陈述,除了最好的情况通常是非常微不足道的,因此本身并不有趣.

此外,请注意f(n)= n = O(n ²) - 这在技术上是正确的,因为f比n ²增长得慢,但它没有用,因为它不是最小的上限 - 有一个非常明显的上限比这个更有用,即O(n).所以,是的,非常欢迎您说程序的最佳/最差/平均情况运行时间是O(n!).这在数学上是完全正确的.它只是没用,因为当人们要求Big-O时,他们对最小上限感兴趣,而不仅仅是随机上限.

值得注意的是,将程序的运行时间描述为f(n)可能还不够.运行时间通常取决于输入本身,而不仅仅取决于其大小.例如,即使是查询也很容易回答,而奇怪的查询需要很长时间才能回答.
在这种情况下,你不能只将f作为n的函数给出- 它也取决于其他变量.最后,请记住,这只是一组数学工具; 你的工作是弄清楚如何将它应用到你的程序中,并找出有趣的东西来衡量.以有用的方式使用工具需要一些创造力,数学也不例外.