math - 如何获得这个函数的大 O、大Ω 和大 Θ？

Question

我有一个函数 f(n) 定义如下：

f(n) = (n-1)(n+1)lg(n+5)/(n+3)

这里， lg 是 log ₂。我想确定这个函数的 big-O、big-Ω 和 big-Θ 值。我将如何解决这个问题？

谢谢！

Answer 1

让我们从简化您的表达式开始：

f(n) = (n-1)(n+1)lg(n+5)/(n+3)

= ((n ² - 1) lg (n + 5)) / (n + 3)

现在，让我们假设加法常数在那里。如果我们删除这些常数，我们得到这个函数 g(n)：

g(n) = n ² lg n / n = n lg n

由于我们不希望这些常数在长期内产生如此大的差异，因此冒险猜测这个函数是 Θ(n log n) 是合理的。我们可以通过取 f(n) / n log n 的极限来证明这一点，因为 n 趋于无穷大。如果我们得到一个非零有限值，那么我们知道 f(n) = Θ(n log n)。

所以让我们试试吧！

lim _{n → ∞} f(n) / n log n

= lim _{n → ∞} (((n ² - 1) lg (n + 5)) / (n + 3)) / n lg n

= lim _{n → ∞} ((n ² - 1) lg (n + 5)) / n lg n (n + 3)

= (lim _{n → ∞} (n ² - 1) / n(n+3)) (lim _{n → ∞} (lg (n + 5) / lg n)

= (lim _{n → ∞} (n ² - 1) / (n ² + n)) (lim _{n → ∞} (lg (n + 5) / lg n)

这两个限制都是 ∞ / ∞ 类型的退化形式，因此我们可以使用 l'Hopital 规则并将每个限制替换为其导数：

lim _{n → ∞} (n ² - 1) / (n ² + n)

= lim _{n → ∞} (2n / 2n + 1)

= 1

和

lim _{n → ∞} lg (n + 5) / lg n

= lim _{n → ∞} (1 / (n+5)) / (1 / n)

= lim _{n → ∞} (n / (n+5))

= 1

因此，我们得到

(lim _{n → ∞} (n ² - 1) / (n ² + n)) (lim _{n → ∞} (lg (n + 5) / lg n)

= 1

因此，当 n 趋于无穷大时，f(n) / n lg n 的比率趋向于 1，因此我们有 f(n) = Θ(n log n)，这是需要的。因此，我们还得到 f(n) = O(n log n) 和 f(n) = Ω(n log n)。我们也有 f(n) ~ n log n，这是一个更强有力的主张。

希望这可以帮助！