Re: 1/4
Publié : mer. avr. 01, 2020 10:01 am
Pour FIbonacci, on calcule une expression explicite des termes de la suite par résolution de l'équation caractéristique qui est : X^2-X-1=0.
On trouve deux racines, dont une seule (qui s'avère être le nombre d'or) est plus grande que 1 en valeur absolue, et on a donc un équivalent de la forme : x_n ~ a*phi^n (où \phi=(1+\sqrt(5))/2 est le nombre d'or).
On déduit donc la taille des termes de la suite en passant au log : taille(x_n) = n*ln(\phi)
Et donc le calcul de x_n à partir de x_{n-1} et x_{n-2} est en : max(taille(x_{n-1}),taille(x_{n-2})) = taille(x_{n-1}) = (n-1)*ln(\phi)
Et finalement, le calcul de x_n a un coût en : \sum_{k=0}^{n-1} k*ln(\phi) = n(n-1)/2 * ln(\phi) = O(n^2)
On trouve deux racines, dont une seule (qui s'avère être le nombre d'or) est plus grande que 1 en valeur absolue, et on a donc un équivalent de la forme : x_n ~ a*phi^n (où \phi=(1+\sqrt(5))/2 est le nombre d'or).
On déduit donc la taille des termes de la suite en passant au log : taille(x_n) = n*ln(\phi)
Et donc le calcul de x_n à partir de x_{n-1} et x_{n-2} est en : max(taille(x_{n-1}),taille(x_{n-2})) = taille(x_{n-1}) = (n-1)*ln(\phi)
Et finalement, le calcul de x_n a un coût en : \sum_{k=0}^{n-1} k*ln(\phi) = n(n-1)/2 * ln(\phi) = O(n^2)