performance - 如何确定某物是否是大 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-> infinity 的极限中，然后求解.. 但这给了我每一个都为 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只是一种形式。