一个时间复杂度为O(n)的算法如何同时是O(n^2), O(n^1000000), O(2^n)？

Question

所以，对于这个问题Θ(n)和O(n)之间的区别是什么？的答案是：“基本上，当我们说一个算法是O（n）时，它也是O（n ² ），O（n ^1000000 ），O（2 ⁿ ），... ，但 Θ（n）算法不是Θ（n ²）。 ”

我了解Big O表示上限或最坏情况，但我不理解O（n）也是O（n ² ）和其他比O（n）更糟糕的情况。

也许我有一些基本误解。请帮助我理解这个问题，因为我已经挣扎了一段时间。

谢谢。

- Yadrif

---

如果一个数字小于1，那么它也小于10和1000，但如果它等于1，则不等于10或1000。 - tobias_k

一个上界不一定要非常紧。就像0.99 < 1，但是也0.99 < 100000000000一样，你可以说n=O(n)，但也可以n=O(n³)。BigO是一个上限。BigΘ更像是一个相等关系。 - user1196549

大O符号是一个估算。如果一个算法“在n的范围内”，那么它就是大O(n)。n²是更大的范围，等等。 - AndyG

如果某件事情可以在不超过n的时间内完成，那么它也可以在n^2的时间内完成，因为n < n^2。这就是为什么O(n)算法也是O(n^2)的原因。 - shuttle87

Answer 1

思考大O表示法的含义非常有帮助：如果一个函数是O(n)，那么，其中c是正数，是上界。如果是一个上界，那么很明显对于整数，也将是一个上界，同样，，等都是上界。

下面的图表显示了函数的增长，它们是它右边的函数的上界；即在更小的上增长得更快。

- erip

Answer 2

假设您的算法运行时间为 T(n) = 3n + 6（即一阶任意多项式）。

根据大O符号的定义，对于所有 n > 5，3n + 6 < 4n，因此T(n) = O(n)。同样地，3n + 6 < n^2 对于所有 n > 5，因此T(n) = O(n^2)。

同样可以证明T(n) = Θ(n)，因为除了证明它是O(n)之外，对于所有的n > 1，3n + 6 > n也是成立的。然而，无法证明对于任意大的n和任何值的c都有3n + 6 > c n^2。（证明简述：当n -> infinity时，lim (cn^2 - 3n -6) > 0）。

- chepner

Answer 3

我理解Big O表示上限或最坏情况，但我不明白为什么O(n)也是O(n²)，而其他情况比O(n)更糟糕。

直观地说，“x的上限”意味着某些东西将始终小于或等于x。如果某物小于或等于x，则对于足够大的x值，它也小于或等于x²和x^1000。因此，x²和x^1000也可以是上限。

这就是Big-oh所代表的：上限。

- IVlad

---

从技术上来说，它的意思是“不超过”。 - Scott Hunter

Answer 4

当我们说f(n) = O(g(n))时，我们仅意味着对于所有足够大的n，存在一个常数c使得f(n) <= cg(n)。请注意，如果f(n) = O(g(n))，我们总是可以选择一个比g(n)更大的函数h(n)，由于g(n)最终小于h(n)，因此我们有f(n) <= cg(n) <= ch(n)，因此f(n) = O(h(n))。

请注意，O边界不是紧密的。theta边界是O(g(n))和Omega(g(n))的交集，其中Omega给出下限（它类似于O，上限，但从下面限制）。如果f(n)受到g(n)的下限约束，并且h(n)大于g(n)，那么就会得出结论，f(n)不一定受到h(n)的下限约束。

- Patrick87