math - ステートメントの大きな O の証明

Question

n^kそれがO(2^n)すべての人に当てはまることを証明するのに苦労していますk。lg2両面取ってみたのk*lgn=nですが、これは違います。これを他にどのように証明できるかわかりません。

Answer 1

n ^kが O(2 ⁿ ) であることを示すには、

n ^k = (2 ^{lg n} ) ^k = 2 ^{k lg n}

したがって、すべての n ≥ n ₀に対して、 n ₀と cを見つけたいとします。

2 ^{k lg n} ≤ c 2 ⁿ

^{ここで、c = 1 として、ある m に対して n = 2 m}の場合に何が起こるかを考えてみましょう。これを行うと、

2 ^{k lg n} ≤ c 2 ⁿ = 2 ⁿ

2 ^{k lg 2 m} ≤ 2 ^{2 m}

2km ≦ ^{2 2m _}

そして、2 ⁿは単調増加関数なので、これは

km≦ ^2m

さて、物事を終わらせましょう。m = max{k, 4} とすると、k ≤ m となります。したがって、私たちはそれを持っています

km≦ ^m2

私たちもそれを持っています

m2 ≦ ^{2m _}

任意の m ≥ 4 に対して、m ² ≤ 2 ^mであるため、m の選択によって、m = max{k, 4} が保証されます。これを組み合わせると、

km≦ ^2m

これは、上で示したかったものと同等です。したがって、任意の n ≥ 2 ^m = 2 ^{max{4, k}}を選択すると、n ^k ≤ 2 ⁿとなります。したがって、big-O 記法の正式な定義により、n ^k = O(2 ⁿ ) が得られます。

この計算は正しいと思います。私が間違っている場合はお知らせください！

お役に立てれば！

Answer 2

まだコメントできないので、これを答えにします。

あなたがやろうとしていたように方程式を減らす代わりに、ここにある大きなO表記の正式な定義を満たすann0と aを見つけようとする必要があります: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definitionM

うまくいくかもしれない行に沿った何かn0=M=k（私はそれを書いていないので、うまくいかないかもしれません、それはあなたにアイデアを与えるためだけです）