复杂性证明
问题描述：
我会证明下面的例子：复杂性证明
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的值是无关紧要......可以吗？
答
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步似乎是错误的，至少我没有看到你从哪里得到它。你的结论似乎也不能证明所要求的。
没有花时间写出来，第3步困扰我，我不相信你可以用日志做到这一点。 （请注意，有没有读过Lamport关于证明的论文？值得一读）。 – 2010-10-05 20:50:17
Paul是正确的，你不能在第3步中使用日志。log（c^n）= n * log（c）。因此，步骤3应该是：（log（n^k））/ n mpd 2010-10-05 21:00:37
Thanx，在步骤3中有一个错误，我写得很快，没有检查它。 – Ian 2010-10-05 21:17:08