algorithm - 哪个算法支配 f(n) 或 (g(n)

Question

我正在上一门算法入门类(class)。我遇到了这个我不确定的问题。我想知道这 2 个中哪个占主导地位

f(n): 100n + log n 或 g(n): n + (log n)^2

给定每个的定义:Ω, Θ, O

我假设 f(n)，所以 fn = Ω(g(n))原因是 n 支配 (log n)^2，这是真的吗？

Answer 1

在这种情况下，

lim_{n → ∞}[f(n)/g(n)] = 100。

如果你复习微积分定义，这意味着对于任何 ε > 0，存在一些 m

100 (1 - ε) g(n) ≤ f(n) ≤ 100 (1 + ε) g(n)

对于任何 n > m。

根据Θ的定义，可以推断这两个函数互为Θ。

---

一般来说，如果

lim_{n → ∞}[f(n)/g(n)] = c 存在，并且

0 < c < ∞,

那么这两个函数具有相同的增长顺序(它们是彼此的Θ)。