algorithm - 指数関数の伸び率比較？

Question

f(n) = 2 ^{2 ⁿ⁺¹}と g(n)=2 ^{2 ⁿ}という 2 つの関数があるとします。2 つの異なる方法を使用して、これら 2 つの関数の成長率を比較したいと思います。

方法 1: 比率を取る

t(n) = f(n) / g(n) を定義しましょう。それで

t(n) = f(n) / g(n)

= 2 ^{2 ⁿ⁺¹} / 2 ^{2 ⁿ}

= 2 ^{2 ^{n + 1} - 2 ⁿ}

= 2 ^{2 ⁿ}

したがって、f(n) は g(n) よりもはるかに速く成長すると仮定します。

前述のように、t(n) = f(n) / g(n) とします。ここで、両辺の対数底 2 を取りましょう。

lg t(n) = lg (f(n) / g(n))

= lg (2 ^{2 ⁿ⁺¹} / 2 ^{2 ⁿ} )

= lg 2 ^{2 ⁿ⁺¹} - lg 2 ^{2 ⁿ} )

= 2 ⁿ⁺¹ - 2 ⁿ

ここで、両辺の対数底 2 を取りましょう。

lg lg t(n) = (n + 1) lg 2 / n lg 2

= (n + 1) / n

定数項を無視すると、lg lg t(n) = 1 が得られます。これは定数であるため、f(n) と g(n) は同じ成長率を持つ必要があります。

方法 2 を使用すると間違った答えが得られるのはなぜですか?

score 2 · Accepted Answer

あなたのエラーは次のことを前提としていると思います：

log log f(x) / log log g(x) が定数の場合、f(x) = Θ(g(x)) です。

これに対する簡単な反例を次に示します。f(x) = x ²および g(x) = x とします。それで

ログログ f(x) = ログログ x ² = ログ (2 ログ x) = ログ 2 + ログログ x

と

対数対数 g(x) =対数対数 x

ここで、対数対数 f(x) と対数対数 g(x) は定数 (つまり、対数 2) だけ異なりますが、明らかに、f(x) と g(x) が同じ速度で成長するということは正しくありません。つまり、2 つの関数の成長率のログを取得した後で定数を無視するのは安全ではありません。

ロジックに 2 番目のエラーがあります。f(n) / g(n) を計算すると、

2 ^{2 ^{n + 1}} / 2 ^{2 ⁿ}

= 2 ^{2 ⁿ⁺¹ - 2 ⁿ}

= 2 ^{2 ⁿ}

このログを 2 回取得すると、次のようになります。

lg lg 2 ^{2 ⁿ}

= lg 2 ⁿ

= n

したがって、比率の対数対数が (n + 1) / n であるというのは真実ではありません。代わりに、それはまだ無限に向かって進む傾向がある n です。これは、f(n) が g(n) よりもはるかに急速に成長することも示しています。

お役に立てれば！