以下函数的时间复杂度为O(n³)是什么意思？

Question

以下函数的时间复杂度为O(n³)是什么意思？

algorithmtime-complexitybig-oasymptotic-complexity

3

我正在通过Coursera上的斯坦福大学算法讲座系列（Tim Roughgarden主讲）学习。在那里，他提出了一个多项选择题，以找到下面图像中给出的函数的运行时间复杂度。

在这个问题中，最后三个选项都是正确的。我理解Ω（Omega）和Θ（Theta）的前两个选项只需要看函数就可以了，但是我无法理解为什么最后一个选项是正确的，因为据我所知，运行时间复杂度应该是O(n^2)而不是O(n^3)。

请问有人能解释一下我错在哪里吗？

- KhiladiBhaiyya

你使用的是什么大O符号的定义？如果你不能在查阅资料的情况下回忆起定义，那你是怎么得出答案的呢？ - Paul Hankin

在这种情况下，这三个符号表示不同的含义。大Omega O(n)是最好的情况，接下来是大Theta O(n^2)是平均情况，最后，大oh O(n^3)是最坏的情况。这就是为什么它们都是正确的。因为对于所有输入，该函数最多可以是O(n^3)，最少为O(n)。 - MichaelMMeskhi

你的问题似乎更适合在计算机科学上提问。据我所知，你也可以在那里使用LaTeX，这样所有的数学公式都会变得更容易阅读。 - cadaniluk

5个回答

1

为了数学上的精确性，大O、大Omega等都是集合而不是函数。因此，当我们说T(n) = O(n^3)时，我们实际上是指T(n)在集合O(n^3)中。但由于很难排版“在集合中”的符号，我们通常只写T(n) = O(n^3)。因此，这会引起一些混淆，但基本上O(n^3)只是不比n^3增长得更快的函数的集合。当然，给定的T(n)不会比n^3增长得更快，因此T(n)在集合O(n^3)中。

同样地，T(n)也在集合O(n^4)，O(n^5)，O(n^3 log n)，O(n^127)，O(n^n^n)等中。

因此，如果问题中有第五个选项：T(n) = O(n^2)，那么也是正确的。

- Amrinder Arora

请解释为什么答案不是O(n^2)，我无法理解它。 - KhiladiBhaiyya

@DG4 答案是O(n^2)、O(n^3)和O(n^4)...等等。每个后续集合都比前一个集合大，因此所有这些都是正确的答案。这只是数学上说给定函数不会比n^2增长得更快，它也不会比n^3增长得更快，它也不会比n^4增长得更快...等等。 - Amrinder Arora

1

首先，我建议不要将渐进界限视为计算机科学的一部分；它是一种数学工具。不要将“大O符号”严格与“最坏情况”等联系起来。大O符号给出了一个渐进上界。就是这样。在计算机科学中，它恰好用于描述算法的最坏情况运行时间，但这是数学而不是计算机科学所描述的。

但这只是我的意见，要注意。

以下是 Big O 符号的定义（这是我最先学习到的正式定义）：
来自算法导论第三版（我也正在通过这本书学习算法），第47页：

对于给定的函数 g(n)，我们用 O(g(n)) [...] 表示函数集合

O(g(n)) = { f(n) : 存在正常数 c 和 n₀，使得对所有 n ≥ n₀，都有 0 ≤ f(n) ≤ cg(n) }。

观察大O符号表示一个集合，因此它可以是一个更大的超集的一部分，并且可以是其他子集的超集。写成“n = O(n)”只是一个形式上不正确的说法，即函数f(n) = n是集合O(n)（n ∈ O(n)）的成员。
滥用大O符号（即将其放在方程中）可以使我们在方程中使用它，并写出像T(n) = 1/2n + O(n)这样的东西，这基本上意味着T(n)等于1/2n再加上某个函数，该函数的大O符号定义如上所述成立。

那么，你想知道为什么像n² = O(n³)这样的东西吗？让我们通过我们的正式定义来展示：

g(n) = n³
f(n) = n²

对于所有n ≥ n₀，都有0 ≤ n² ≤ cn³

直观地说，我们可以很容易地看出这个不等式必须存在一些c和n₀（实际上，c ≥ 1且n₀= 0）才能成立，因为一个三次函数增长的渐近速度比一个二次函数要快。

对于g(n) = n²也是同样的道理，你会看到n² = O(n²)同样成立（对于c ≥ 1和n₀= 0）。

所以，n² = O(n³) 并且 n² = O(n²)？这是可能的，因为O(n³)和O(n²)不是不相交的；O(n²)是O(n³)的子集，因为每个二次函数都可以被上界为一个三次函数。

正如你所看到的，渐近界限不一定是紧密的; n = O(n⁶⁵⁵³⁶)是真实的。然而，显然更喜欢紧密的界限。

- cadaniluk

0

如果你能证明它是O(n^2)（为了证明它是Big Theta(n^2)，你必须这样做。不要仅仅通过“看它”来做，要进行数学计算），那么在证明中将所有出现的n^2替换为n^3。

这个证明还正确吗？

记住，大O表示上界。

- IVlad

@IVIad，你能展示一下如何数学证明吗？因为我不知道该怎么做。 - KhiladiBhaiyya

0

T(n) = O(n^2) <=> 存在常数 c > 0, n0 >= 0，使得对于所有的 n >= n0，都有 T(n) <= c.n^2。

现在，c.n^2 <= c.n^3 对于所有的 n > 1 成立（一个恒等式）

=> T(n) <= c.n^2 <= c.n^3 对于所有的 n >= n1 = max(n0, 1)

=> 存在常数 c > 0, n1 = max(n0, 1)，使得 T(n) <= c.n^3

=>     T(n) = O(n^3)

实际上，我们可以证明对于所有的n>=2（例如使用归纳法），T(n)=O(n^2) => T(n)=O(n^k)。

- Sandipan Dey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cilenco · Accepted Answer

O(n^2) 是 O(n^3) 的子集。维基百科对此有很好的解释。

事实上，如果 lim |f(x)|/g(x) 小于无穷大（n趋近于无穷大），则 f(n) 属于 O(g(n))。在这里，它将是

O(1/2*n^2+3n) is in O(n^3) 
<=> lim |(1/2*n^2+3n)| / n^3
<=> lim |(n*[n/2 + 3])| / n^3
<=> lim |(n/2 + 3)| / n^2 < infinty

for n to infinity n^2 is allways greater then n/2 so for positiv n this goes against 0

另一种证明方法是：你能找到一个正整数k和c，使得f(n)始终小于k*g(n)+c（并非对于所有的n都成立-如果对于一个n0及其之后的所有数字都成立，则足够）。在这里，您可以选择k=1和c=0，因为如前所述，对于正整数n，n^2始终小于n^3。

这里有一个很好的O符号的Veen图示。