Pourquoi la complexité du calcul de la série Fibonacci 2^N et non n^2?
9 réponses
La complexité d'un fibonacci récursif naïf est en effet 2ⁿ.
T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) =
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...
Dans chaque étape, vous appelez T deux fois, fournira ainsi une barrière asymptotique éventuelle de:T(n) = 2⋅2⋅...⋅2 = 2ⁿ
Bonus : la meilleure implémentation théorique de fibonacci est en fait une formule close , en utilisant le Nombre d'or :
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]
(cependant, il souffre d'erreurs de précision dans la vie réelle en raison de l'arithmétique à virgule flottante, qui ne sont pas exactes)
L'arbre de récursivité pour fib (n) serait quelque chose comme:
n
/ \
n-1 n-2 --------- maximum 2^1 additions
/ \ / \
n-2 n-3 n-3 n-4 -------- maximum 2^2 additions
/ \
n-3 n-4 -------- maximum 2^3 additions
........
-------- maximum 2^(n-1) additions
- en utilisant n-1 dans 2^(n-1) puisque pour fib (5) Nous finirons par descendre à fib (1)
- Nombre de nœuds internes = Nombre de feuilles - 1 = 2^(n-1) - 1
- Nombre d'ajouts = Nombre de nœuds internes + Nombre de feuilles = (2^1 + 2^2 + 2^3 + ...) + 2^(n-1)
- nous pouvons remplacer le nombre de nœuds internes par 2^(n-1) - 1 car il sera toujours inférieur à cette valeur : = 2^(n-1) - 1 + 2^(n-1) ~ 2 ^ n
Regarde ça comme ça. Supposons que la complexité du calcul de F(k), le nombre kth Fibonacci, par récursion est au plus 2^k pour k <= n. C'est notre hypothèse d'induction. Alors la complexité du calcul F(n + 1) par récursion est
F(n + 1) = F(n) + F(n - 1)
Qui a de la complexité 2^n + 2^(n - 1). Notez que
2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).
Nous Avons montré par induction que l'affirmation selon laquelle le calcul de F(k) par récursivité est au plus 2^k est correcte.
Vous avez raison de dire que la profondeur de l'arbre est O (n), mais vous ne faites pas de travail O(n) à chaque niveau. A chaque niveau, vous faites O(1) travail par appel récursif, mais chaque appel récursif contribue alors deux nouveaux appels récursifs, un au niveau en dessous et un au niveau deux en dessous. Cela signifie que lorsque vous descendez de plus en plus dans l'arbre de récursivité, le nombre d'appels par niveau augmente de façon exponentielle.
Fait intéressant, vous pouvez effectivement établir le nombre exact d'appels nécessaires pour calculer F (n) comme 2F (n + 1) - 1, où F(N) est le nième nombre de Fibonacci. Nous pouvons le prouver inductivement. En tant que cas de base, pour calculer F(0) ou F(1), nous devons faire exactement un appel à la fonction, qui se termine sans faire de nouveaux appels. Disons que L(n) est le nombre d'appels nécessaires pour calculer F(n). Ensuite, nous avons que
L(0) = 1 = 2*1 - 1 = 2F(1) - 1 = 2F(0 + 1) - 1
L(1) = 1 = 2*1 - 1 = 2F(2) - 1 = 2F(1 + 1) - 1
Maintenant, pour le étape inductive, supposons que pour tous n '
1 + L(n - 1) + L(n - 2)
= 1 + 2F((n - 1) + 1) - 1 + 2F((n - 2) + 1) - 1
= 2F (n) + 2F (n-1) - 1
= 2 (F (n) + F (N-1)) - 1
= 2(F (N + 1)) - 1
= 2F (n + 1) - 1
Qui complète l'induction.
À ce stade, vous pouvez utiliser la formule de Binet pour montrer que
L(n) = 2(1/√5)(((1 + √5) / 2)n - ((1 - √5) / 2)n) - 1
Et donc L(n) = O(((1 + √5) / 2)n). Si nous utilisons la convention que
Φ = (1 + √5) / 2 &environ; 1,6
Nous avoir ça
L(n) = Θ(φn)
Et puisque φ n ) (en utilisant la notation little-o).
Fait intéressant, j'ai choisi le nom L (n) pour cette série parce que cette série s'appelle les numéros Leonardo. En plus de son utilisation ici, il se pose dans l'analyse de la smoothsort algorithme.
J'espère que cela aide!
T(n)=t(n-1)+t(n-2) qui peut être résolu par la méthode de l'arbre:
t(n-1) + t(n-2) 2^1=2
| |
t(n-2)+t(n-3) t(n-3)+t(n-4) 2^2=4
. . 2^3=8
. . .
. . .
De même pour le dernier niveau . . 2 ^ n
cela rendra la complexité totale du temps=>2+4+8+.....2 ^ n
après avoir résolu le gp ci-dessus, nous obtiendrons la complexité du temps comme O (2^N)
La complexité de la série de Fibonacci est O (F (k)), où F (k) est le kème nombre de Fibonacci. Cela peut être prouvé par induction. C'est trivial pour le cas basé. Et supposons que pour tout k
La complexité O(2^N) du calcul des nombres de Fibonacci ne s'applique qu'à l'approche de récursivité. Avec un peu d'espace supplémentaire, vous pouvez obtenir une bien meilleure performance avec O (n).
public static int fibonacci(int n) throws Exception {
if (n < 0)
throws new Exception("Can't be a negative integer")
if (n <= 1)
return n;
int s = 0, s1 = 0, s2 = 1;
for(int i= 2; i<=n; i++) {
s = s1 + s2;
s1 = s2;
s2 = s;
}
return s;
}
La complexité des séries récursives de Fibonacci est 2^n:
Ce seront les relations de récurrence pour Fibonacci récursif
T(n)=T(n-1)+T(n-2) No of elements 2
Maintenant sur la résolution de cette relation en utilisant la méthode de substitution(en substituant la valeur de T(n-1) et T (N-2))
T(n)=T(n-2)+2*T(n-3)+T(n-4) No of elements 4=2^2
En substituant à nouveau les valeurs du terme ci-dessus, nous obtiendrons
T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6) No of elements 8=2^3
Après l'avoir résolu complètement, nous obtenons
T(n)={T(n-k)+---------+---------}----------------------------->2^k eq(3)
Cela implique que le nombre maximum d'appels récursifs à n'importe quel niveau sera au plus de 2^n.
Et pour tous les les appels récursifs dans l'équation 3 Sont Θ (1), donc la complexité temporelle sera 2^n* ϴ(1)=2^n
Je ne peux pas résister à la tentation de connecter un algorithme itératif en temps linéaire pour Fib au temps récursif exponentiel: si l'on lit le merveilleux petit livre de Jon Bentley sur "Écrire des algorithmes efficaces", je crois que c'est un cas simple de "mise en cache": chaque fois que Fib(k) est calculé, stockez-le dans le tableau FibCached[k]. Chaque fois que Fib(j) est appelé, Vérifiez d'abord s'il est mis en cache dans FibCached[J]; si oui, renvoyez la valeur; sinon, utilisez la récursivité. (Regardez l'arbre des appels reçus ...)