proof - 複雑性の証明

Question

次の例を証明したいと思います。

n^k = O (c^n) for every k and c>1

多項式関数が指数関数よりも速く成長することは注目に値します。条件を満たす k0 > 0 を見つけようとします。

fn > = k0 * g(n)

よりも

n^k <= k0 * c^n
log(n^k) <= log (k0 * c^n)
log(n^(k/n)) <= log (k0 * c)
k0 >= 1/c*n^(k/n)

したがって、k0 > 0、正で十分に小さいですが、c の値は関係ありません... OK ですか?

Answer 1

log(n^k) <= log (k0 * c^n)
k log n <= log k0 + n log c

k log n - n log c <= log k0
log (n^k) - log (c^n) <= log k0
log ((n^k) / (c^n)) <= log k0 | expo
(n^k) / (c^n) <= k0
n^k <= k0 * c^n

=> n^k = O(c^n)

あなたのステップ 3 は間違っているようですが、少なくともどこから入手したのかわかりません。あなたの結論も、求められていることを証明していないようです。