以下函数 O(n³) 的时间复杂度如何？

Question

我正在听 Tim Roughgarden 在 Coursera 上的斯坦福大学算法讲座系列。在那里，他给出了一个多项选择题来计算函数的运行时间复杂度，如下图所示。

本题最后三个选项正确。仅通过查看函数，我就理解了 Ω (Omega) 和 Θ (Theta) 的前两个选项是如何正确的，但是我无法理解最后一个选项是如何正确的，因为据我所知，运行时间复杂度应该是 O(n²) 而不是 O(n³).

谁能解释一下我哪里错了？

Answer 1

如果你能证明它是 O(n^2)（你必须证明它是 Big Theta(n^2)。不要仅仅通过 "looking at it" 来证明它，做数学。），然后在证明中用 n^3 替换所有出现的 n^2 。

现在还正确吗？

请记住 Big-oh 是上限。

Answer 2

O(n^2) 是 O(n^3) 的子集。 Wikipedia 适合这个。

事实上，如果 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 和所有大于 n0 的数字都是如此就足够了。在这里你可以选择 k=1 和 c=0 因为如前所述，n^2 总是小于 n^3 正数 n.

Here 是 O 表示法 Veen-Diagram.

的一张很好的图片

Answer 3

准确地说，big O、big Omega 等都是集合，不是函数。所以，当我们说 T(n) = O(n^3) 时，我们实际上是指 T(n) 在集合 O(n^3) 中。但是由于排版 "in the set" 符号并不容易，我们通常最终会写成 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)，那也是正确的。

Answer 4

首先，我建议不要将渐近边界视为计算机科学的一部分；它是一种数学工具。不要将 "Big O" 与 "worst case" 等严格关联。大 O 给出了一个 渐近上限 。而已。它恰好在计算机科学中用于描述算法的最坏情况运行时间，但描述其工作原理的是数学，而不是计算机科学。
但这只是我的意见，请注意。

将此定义用于大 O 表示法。（这是我最先学到的正式定义。）
来自 Introduction to Algorithms 3^rd Edition（我自己仍在通过那本书学习算法），第 47 页：

For a given function g(n), we denote by O(g(n)) [...] the set of functions

O(g(n)) = { f(n) : there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n₀ }.

Observe Big O notation 表示一个 set 因此，它可以是 superset 的一部分并且它可以是一个超集其他 个子集 。写作 "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²

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

凭直觉，我们很容易看出一定有c和n₀（实际上c≥1和n₀ = 0) 因为三次函数比二次函数渐近增长得更快，所以这个不等式成立。

对 g(n) = n² 做同样的事情，你会看到 n² = O(n²) 以及（对于 c ≥ 1 和 n₀ = 0）。

所以，n² = O(n³) and n² = O(n²)?这是可能的，因为 O(n³) 和 O(n²) 不相交； O(n²) 是 O(n³) 的子集，因为每个二次函数都可以由三次函数从上方界定。

如您所见，渐近边界不需要紧； n = O(n⁶⁵⁵³⁶) 是 true。然而，紧边界显然是首选。

Answer 5

T(n) = O(n^2) <=> 存在常量 c > 0, n0 >= 0 s.t。 T(n) <= c.n^2 所有 n >= n0.

现在，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)、s.t。 T(n) <= c.n^3

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

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

以下函数 O(n³) 的时间复杂度如何？

How is the time complexity of the following function O(n³)?

algorithm

big-o

time-complexity

asymptotic-complexity