Je suis d'accord avec pgaur et rickerbh, récursif de fibonacci de la complexité est O(2^n).
Je suis venu à la même conclusion par un peu simpliste, mais je crois toujours valide le raisonnement.
Tout d'abord, il est tout au sujet de trouver comment beaucoup de fois récursif de la fonction de fibonacci F() à partir de maintenant ) est appelée lors du calcul du n-ième nombre de fibonacci. Si elle est appelée une fois par numéro dans la séquence de 0 à n, alors nous avons O(n), s'il est appelé à la n des temps, pour chaque numéro, alors on obtient O(n*n) ou O(n^2), et ainsi de suite.
Ainsi, lorsque F() est appelée pour un nombre n, le nombre de fois où F() est appelée pour un nombre entre 0 et n-1 grandit à mesure que nous nous approchons de 0.
Comme première impression, il me semble que si on le met dans un mode visuel, le dessin d'une unité en fonction du temps F() est appelée pour un nombre donné, humide obtenir une sorte de forme de pyramide (qui est, si nous centre unités horizontalement). Quelque chose comme ceci:
n *
n-1 **
n-2 ****
...
2 ***********
1 ******************
0 ***************************
Maintenant, la question est de savoir quelle est la vitesse de base de cette pyramide élargissant à mesure que n augmente?
Prenons un cas concret, par exemple F(6)
F(6) * <-- only once
F(5) * <-- only once too
F(4) **
F(3) ****
F(2) ********
F(1) **************** <-- 16
F(0) ******************************** <-- 32
Nous voyons F(0) est appelée 32 fois, ce qui est 2^5, qui, pour cet échantillon est de 2^(n-1).
Maintenant, nous voulons savoir combien de fois F(x) est appelée à tous, et nous pouvons voir le nombre de fois que F(0) est appelée n'est qu'une partie de cela.
Si nous mentalement déplacer tous les *'partir de F(6) F(2) les lignes en F(1), nous voyons que F(1) et F(0) sont maintenant égaux en longueur. Ce qui signifie, le temps total F() est appelée lorsque n=6 est 2x32=64=2^6.
Maintenant, en termes de complexité:
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)