math - big-O 表記の指数

Question

3 ⁿ = O(2 ⁿ ) ですか? (3/2) ⁿ = O(2 ⁿ ) はどうですか? 答えを説明できますか？

^{2 n}にどのような定数 C を掛けても、3 ^{nは 2 n}よりも速く成長するため、最初は false になりました。2番目も同じですか？

log(3 ⁿ ) = O(log (2 ⁿ ) ) はどうですか? ログのベースがわからないため、これを特定できないと思います。

Answer 1

より強い結果を実際に証明してみましょう: 1 ≤ r ₀ < r _{1である任意の定数 r 0}および r _{1について、r 0} ⁿ = O(r ₁ ⁿ )は真であり、r ₁ ⁿ = r ₀ ⁿは偽です。 . 1 < 3/2 < 2 であるため、これは特殊なケースとして結果を証明します。

最初の部分を証明するために、r ₀ ⁿ = O(r ₁ ⁿ ) であることを示します。これを行うには、big-O の定義を使用し、任意の n > n _{0 に対して}、次のようになる n ₀と cの値を見つけます。

r ₀ ⁿ ≤ cr ₁ ⁿ

n = n ₀を選択でき、c = 1 を選択できます。上記の不等式が成立するため、定義により、r ₀ ⁿ = O(r ₁ ⁿ ) が得られます。

2 番目の部分を証明するために、r ₁ ⁿ ≠ O(r ₀ ⁿ ) であることを示します。これを行うには、矛盾を進めます。矛盾を避けるために、任意の n > n ₀に対してc と n ₀の選択が存在すると仮定します。

r1n ≦ _cr0n ^_ _{_} ^_

両側のログを取る

n log r ₁ ≤ log (cr ₀ ⁿ )

n log r ₁ ≤ log c + n log r ₀

n (log r ₁ - log r ₀ ) ≤ log c

n log(r ₁ / r ₀ ) ≤ log c

n ≤ log c / (log(r ₁ / r ₀ ))

しかし、このステートメントは n の任意の選択に対して成り立つ必要があるため、問題が発生しています。_{ただし、log c / (log(r 1} / r ₀ ))より大きい n を選択すると、ステートメントは偽になります。

矛盾に達したので、仮定が間違っていたに違いありません。したがって、1 < r ₀ < r ₁の場合、r ₁ ⁿ ≠ O(r ₀ ⁿ ) となります。

お役に立てれば！