algorithm - 寻找 Big-O、Omega 和 theta

Question

我浏览了这些链接，但我太脑残了，无法理解找出它们的机械过程。我了解 O、theta 和 omega 的想法，我了解“规则”。所以让我和你们一起研究这个例子，在我的脑海中理清这个问题:)

f(n) = 100n+logn

g(n) = n+(logn)2

我需要找到:是 f = O(g)，还是 f = Ω(g)，或两者(在这种情况下 f = Θ(g))

所以我知道 100n 和 n 是一样的，它们都比 log(n) 慢。我只需要弄清楚 (log(n))^2 是慢还是快。但我真的不记得关于日志的任何事情。如果 log(n) 更大，是否意味着数字变大或变小？

让我补充一下，我真正的困难在于弄清楚 omega 和 theta。根据定义 f(n) <= g(n) 如果有一个常量 c 会使 g(n) 更大，对于 omega 则相反。但我该如何真正测试呢？

Answer 1

你通常可以从这些规则中弄清楚:

1. 广义 k < log(n)^k < n^k < k^n .您可以替换 k在每个步骤中使用您想要的任何正数，并且对于足够大的情况仍然如此 n .

2. 如果 x很大，那么1/x非常接近于 0。

3. 对于正 x和 y , x < y当且仅当 log(x) < log(y) . (有时记录日志可以帮助处理复杂和困惑的产品。

4. log(k^n) = log(k) n .

5. 对于 O、theta 和 omega，您可以忽略除未抵消的最大项之外的所有项。

规则 1 和 5 足以解决您的具体问题。但要了解所有规则。