以下函数如何 O(N^3)？

Question

我正在 Coursera 上学习 "Intro To Algorithms" 课程，我已经看到了处理 Big-Theta、Big-Omega 和 Big-O 符号的视频。视频结尾的测验提出了以下问题：

Q: Which of the following functions is O(N^3)?

a) 11N + 15lgN + 100
b) (N^2)/3
c) 25,000*(N^3)
d) All of the above

我回答了 "c"，但被告知我的答案不正确，而正确答案实际上是 "d"。课程提供的解释并没有多大帮助：

Recall that big-Oh notation provides only an upper bound on the growth
rate of a function as N gets large. In this course, we primarily use 
tilde notation because it more accurately describes the function—it 
provides both an upper and lower bound on the function as well as the 
coefficient of the leading term.

我的印象是应该放弃低阶项（即“15lgN + 100”）并只关注最高阶项。此外，我看不出 N^3 如何成为像 N^2 这样的二次（而不是三次）函数的上限。

所以我的问题是，为什么在这种情况下 "a" 和 "b" 被分类为 O(N^3)？

Answer 1

你知道吗，f(n) = O(g(n))意味着f(n) <= constant* g(n)，对吧？换句话说，这意味着，当您绘制 f(n) 和 g(n) 的图形时，经过某个值后，g(n) 将始终大于 f(n).

这里 g(n) 是 N^3，剩下的是 f(n)。现在，N^3 总是 >= 选项 a、b、c。因此回答 ID D :)

编辑： 以下陈述是正确的，

n=O(n)
n=O(n^2)
n=O(n^3)

但只有 n = O(n) 是严格的上限，这是我们在算法的时间复杂度推导中应该使用的。如果我们使用第二个和第三个选项，那么我们就误用了大 O 符号，或者说它们是上界但不是紧界！

编辑2：见下图

G(x) 是 F(x) 的紧上限，而 H(x) 是 F(x) 的上限但不紧！我们仍然会说，F(x)=O(G(x)) & F(x)=O(H(x))。当 exam/interview 中的某人要求时间复杂度时，他们要求的是严格的界限，而不是上限。不幸的是，紧上限和上限术语在 exams/interviews 中可以互换使用。

Answer 2

想想 O(N^2) 也是 O(n^3)、O(n^4) 等等。 O(N^2) 总是受 O(n^3) 约束，因此 O(n^2) 确实是 O(n^3)。

http://en.wikipedia.org/wiki/Big_O_notation#/media/File:Big-O-notation.png

Answer 3

许多人已经引用了一个函数 f(n) ，它具有上限说 O(n) 复杂度也是 O(n^2) ， O(n^3) ， O(n^4) .. .等

这是否有意义，或者如果它感到困惑，请从绝对外行的角度思考。

假设一个进程最多需要 10 秒的上限来执行，无论输入是什么，我们都可以得出这样的结论:-

无论输入什么，执行都将在小于或等于 10 秒内完成。

如果那是真的，那么下面的也是真的:-

无论输入什么，执行都将在小于或等于 100 秒内完成。
无论输入什么，执行都将在小于或等于 1000 秒内完成。

等等......

因此您可以关联答案。希望这能让你一瞥。

Answer 4

解释是这样说的：“回想一下，大 O 符号只提供了增长的上限 N 变大时函数的速率。”

在此特定上下文中，上限可以读作 "does not grow faster than N³"。

确实 11N + 15lgN + 100 的增长速度并不比 N³ 快。

以下函数如何 O(N^3)？

How are the following functions O(N^3)?

algorithm

big-o