Complexité Fibonacci
Résolu/Fermé
A voir également:
- Le mot de passe doit respecter des exigences de complexité grisé
- Piratage facebook changer mot de passe - Guide
- Mot de passe administrateur freebox ✓ - Forum Freebox
- Ce programme est écrit en python. il construit un mot secret dans une variable mais il ne l'affiche pas. modifiez-le pour qu'il affiche le mot secret. exécutez-le. quel est ce mot secret ? ✓ - Forum Python
- Voir mot de passe wifi android - Guide
- Mot de passe administrateur - Guide
13 réponses
Soit u, le nombre d'or et v = 1-u. Alors la complexité (algébrique!) de votre algorithme est C(n) = F(n+1)-1=-1+( u^(n+1)-v^(n+1))/sqrt(5). Donc pour 'grand' n, C(n) = O((1/sqrt(5)).u^(n+1)) car la deuxième terme devient de la pousière. Cette complexité subit une explosion exponentielle. En faite, votre implementation est très naive (vous calculez et recalculez des choses à la volé!). Quitte à utiliser des 'buffers' pour y mettre tes 'grains' consécutifs. comme ça (en maple, par exemple ...) :
fib := proc (n) local j, x, y, z;
x := 0; y := 1;
if n <= 0 then return n end if;
for j from 1 to n-1 do
z := x+y; x := y; y := z
end do; return z
end proc
La complexité est cette fois-ci O(n), donc linéaire !
Plus 'enervant', en remarquant que F(n+k+1)=F(n)F(k)+F(k+1)F(n+1), faites-en un algorithme avec complexité O(log(n)), donc sous-linéaire !
My french is not very good; please forgive me.
Bon courage.
fib := proc (n) local j, x, y, z;
x := 0; y := 1;
if n <= 0 then return n end if;
for j from 1 to n-1 do
z := x+y; x := y; y := z
end do; return z
end proc
La complexité est cette fois-ci O(n), donc linéaire !
Plus 'enervant', en remarquant que F(n+k+1)=F(n)F(k)+F(k+1)F(n+1), faites-en un algorithme avec complexité O(log(n)), donc sous-linéaire !
My french is not very good; please forgive me.
Bon courage.
22 févr. 2010 à 22:20
6 oct. 2010 à 01:18