logo标签列表

算法A的运行时间至少为O(n²) - 为什么这种说法是无意义的？

algorithmbig-oasymptotic-complexity
9

为什么这个语句：

算法A的运行时间至少为O(n²)

是没有意义的？

插入排序算法的运行时间最多为O(n²)，是正确的吗？

我在网络上找了很久，但没有找到一个好的解释。

我还有一个问题：

我知道任何线性函数a⋅n+b都是O(n)和O(n²)。它也是O(n³)吗？

1
你提出这个问题的背景是什么？ - nhahtdh
4
因为你没有提供任何A算法，所以这是毫无意义的。 - aqua
假设算法A是插入排序算法。 - Tanmoy Banerjee
大O符号提供了算法运行时间的上限（最坏情况）。它绝对不是毫无意义的！此外，与算法平均情况分析相比，最坏情况复杂度的分析在大多数情况下更容易。Big O的简明英文解释 - Devendra D. Chavan
1
我将O(n^2)中的“至少”解释为一种不是最坏情况的运行时间，也就是在这个环境下不是一个合适的大O。 - Anders Forsgren
11个回答
16
T(n)：Algo A的运行时间。我们只关心T(n)的上限和下限。
说明：T(n) >= O(n^2) 上限：因为T(n) >= O(n^2)，所以没有关于T(n)的上限信息。
下限：假设f(n) = O(n^2)，则有语句：T(n) >= f(n)，但f(n)可以是任何小于n^2的东西，例如：常数、n...，因此对于T(n)的下限也没有结论。
=> 这个陈述毫无意义。
9
一个原因可能是没有上限的下限并不是非常有用。"至少"意味着在正常情况下它可以是指数级别的。如果你不知道上限，你可能无法在实际应用中使用算法，因为你不知道程序是否会在宇宙结束之前完成。
当正确使用时，大O符号表示一个上限。因此，将下限陈述为大O是滥用符号。
话虽如此，“毫无意义”是一个强烈的词。即使它不够充分，它仍然是有用的信息。如果你提供更多问题的背景，你可以得到更好的帮助。
感谢您的精确回答。如果我将A视为插入排序算法，那么在这种情况下说“算法A的运行时间至少为O（n2）”是否有用？ - Tanmoy Banerjee
另一个疑问：任何形如 an+b 的线性函数都是 O(n)，也是 O(n^2)。那么它是否也是 O(n^3)？ - Tanmoy Banerjee
1
就像我所说的，陈述执行时间的下限是正确和有意义的，只是使用大O符号来表示它通常是不寻常的，因为大O符号通常用于时间复杂度的上限。说“至少是n2”更正式地描述为（大）Omega（n ^ 2），意思是“渐近地受到n ^ 2的下界约束”。因此，除非您的意思是“渐近地受到上界约束”，否则不应使用“O（..）”。http://en.wikipedia.org/wiki/Big_O_notation - Anders Forsgren
你说：“即使不够充分，这也是非常有用的信息。”那么在什么情况下它会有用呢？ - Tanmoy Banerjee
例如，它可以用来论证它是一个优化或替换的候选对象。 - Anders Forsgren
4
一个比喻：
这个陈述有点像是说：“我房子的屋顶高度至少在地面水平线以上。” 虽然是正确的，但完全没有信息量。
很好理解它的想法 +1 - Soner from The Ottoman Empire
1
我知道任何线性函数an+b都是O(n)和O(n^2)，那么它也是O(n^3)吗？
是的。大O符号表示整个函数集合。但我们应该尽可能地使用它来描述一个函数。虽然f(n) = an + b是O(n^2)甚至O(n^3)，但更准确的说法是f(n) = O(n)。
1

O(n^2)是最坏情况，这意味着A的运行时间将为n^2或更快。如果它的运行时间至少为O(n^2)，那么这意味着A可以拥有的最快运行时间至少为O(n^2)。这意味着它也可能比O(n^2)更慢。这些陈述意味着A可以拥有任何可能的运行时间。

0
O-符号，换句话说意味着： 如果对于所有实数C（即实数集），f(x) < C * g(x)，则f(x)属于集合O(g(x))。
也就是说，您的算法不会增长超过二次函数。
0

这并不是毫无意义的，例如当你不知道确切的算法，但你肯定知道它需要O(n^2)次操作时，就可以使用它。

例如，如果一个人不了解排序算法，但明白要对数组进行排序至少需要查看每个元素，那么他可以说“对数组进行排序至少是O(n)”。

0

因为没有人关心最佳情况下它的速度有多快，最坏情况很重要。通常人们更关心在最坏情况下需要多长时间。

0

设 f(n) 为该算法的运行时间。

=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)

对于f(n)来说，这总是成立的，因为运行时间始终为非负数。因此，该语句是多余的。

0
算法A的运行时间至少为O(n²)。
假设算法A的运行时间。
T(n) = O(log n)

从这里我们已经有了

T(n) <= c.log n

至少O(n²)这个语句试图表达的意思是

T(n) <= c.n²
=> c.log n <= c.n²   #for some c>0 and n>=n0

这是很显然的。当我们已经知道 T(n) <= c.logn 时，说 T(n) <= c.n2 并没有增加任何价值。

因此，当我们已经有一个算法的下限或上限时，说该界限至少或最多（分别）从不添加任何我们已经不知道的新信息。

回答您的第二个问题：

我知道任何线性函数 a⋅n+b 都是 O(n) 和 O(n²)。它也是 O(n³) 吗？

是的。根据上限（大O）的定义，这只意味着

a.n+b <= c.n

所以，如果这是真的，那么这也是真的。

a.n+b <= c.n³
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接