下面的函数 O(N^3) 怎么样？

Question

我正在学习 Coursera 上的“算法简介”课程，我已经看到了处理 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)紧上限才是我们在算法的时间复杂度推导中应该使用的。如果我们使用第二个和第三个选项，那么我们就滥用了 Big-O 表示法，或者说它们是上限但不是严格限制的！

编辑2：参见下图

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