math - この関数の big-O、big-Ω、big-Θ を取得するにはどうすればよいですか?

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) であると思い切って推測するのは理にかなっています。n は無限大に向かう傾向があるため、f(n) / n log 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)

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

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

これらの極限は両方ともタイプ ∞ / ∞ の縮退形式であるため、l'Hopital の規則を使用して、それぞれを導関数に置き換えることができます。

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

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

= 1

と

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

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

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

= 1

したがって、

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

= 1

その結果、f(n) / n lg n の比率は、n が無限大になるにつれて 1 に近づく傾向があるため、必要に応じて f(n) = Θ(n log n) となります。このため、f(n) = O(n log n) および f(n) = Ω(n log n) も得られます。f(n) ~ n log n もあり、これはより強力な主張です。

お役に立てれば！