複雜性證明

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步似乎是錯誤的，至少我沒有看到你從哪裏得到它。你的結論似乎也不能證明所要求的。