complexité preuve

Je voudrais prouver l'exemple suivant:complexité preuve

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

Il est à noter que la fonction polynomiale croît plus vite que la fonction exponentielle. Nous essayons de trouver K0> 0 satisfaisant la condition

fn > = k0 * g(n)

Than

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)

Ainsi, K0> 0, assez positif et petit, alors que la valeur de c est hors de propos ... Est-il acceptable?

Source

2010-10-05 Ian

Sans prendre le temps de l'écrire, l'étape 3 me dérange, je ne suis pas convaincu que vous pouvez le faire avec des journaux. (Note: jamais lu le document de Lamport sur les preuves, ça vaut le coup d'être lu). –

Paul a raison, vous ne pouvez pas le faire avec les logs à l'étape 3. log (c^n) = n * log (c). Donc l'étape 3 devrait être: (log (n^k))/n <= log (k0 * c) – mpd

Thanx, il y a une erreur à l'étape 3, je l'ai écrite rapidement et je ne l'ai pas vérifiée. – Ian

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)

Votre étape 3 semble faux, au moins je ne vois pas d'où vous l'avez obtenu. Votre conclusion ne semble pas non plus prouver ce qui a été demandé.

Source

2010-10-05 20:58:17 IVlad

Répondre

Questions connexes