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的值无关紧要……可以吗？

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 步似乎是错误的，至少我不知道您从哪里得到它。您的结论似乎也不能证明所要求的。