performance - 如何确定某物是否是 big Oh 函数的一部分？

Question

我已经做了大约 4 个小时的作业，我已经设法弄清楚了一些关于这个的问题，但我仍然不知道这个问题在说什么:

以下哪些是正确的，哪些是错误的，为什么？

(a) √n^5 ∈ O(n^2)

(b) √n log √n ∈ O(n)

(c) log(n^3) ∈ O(n log n)

(d) 2/n + 4/n^2 ∈ Θ(1/n)

(e) (log_2(n))^.5 ∈ Θ(log(n))

(f) min(700, n^2) ∈ Θ(1)

我的理解是，我应该取 f(n)/g(n) 并将其置于 n-> 无穷大的极限中，然后求解.. 但是对于它们中的每一个，我都会得到 0 ，我知道那是不对的。

我该怎么做？

非常感谢。

Answer 1

因此，您可以通过两种方式想到这一点。一种是你表示的方式，f(n)/g(n)，作为n->无穷大，值接近0。或者我认为更简单的方式:

There is some pair of constants A and B such that A * g(n) + B > f(n) for all n.  

这更好地代表了 Big-O 符号代表的内容，即一个函数增长消耗另一个函数增长。这也恰好是大 O 符号的表示，可以使用图形计算器轻松检查，以确认您的答案:)。

您通常可以忽略 B 值，只需确保 A*g(n) 比 f(n) 增长得更快。 B 只是一种形式。