Complexité temporelle
lolita-01
Messages postés
90
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
Bonjour,
j'ai pas réussi a trouver la complexité temporelle de cette algo, quelqu'un pourrait m'aider svp
fonction fib-rec(n:entier):entier
debut
si n<2 alors
return n
sinon
return fib-rec(n-1)+fib-rec(n-2)
fin si
Fin
j'ai pas réussi a trouver la complexité temporelle de cette algo, quelqu'un pourrait m'aider svp
fonction fib-rec(n:entier):entier
debut
si n<2 alors
return n
sinon
return fib-rec(n-1)+fib-rec(n-2)
fin si
Fin
A voir également:
- Complexité temporelle
- Ce mot de passe ne répond pas aux critères de longueur, de complexité, de date ou d'historique de la stratégie de mot de passe de votre entreprise. - Forum Windows
- [2003 Server] Mot de passe refusé ! - Forum Windows
- [Active Directory] Problème de mot de passe ✓ - Forum Windows serveur
- Une restriction de compte d'utilisateur (ex. une restriction temporelle) - Forum Windows serveur
- Complexité - Forum VB / VBA
1 réponse
Au final ce que tu fais ce n'est qu'une succession d'addition de +1 ou de +0. Donc la complexité de cet algorithme est de l'ordre du résultat qui est donné par la fonction, c'est donc exponentiel.
Plus précisément, si f=fib-rec(n), alors le nombre d'appels que tu fais peut aller jusqu'à (1+√5)×f, ce qui signifie que tu fais f additions +1 et √5×f additions +0 totalement inutiles.
Mais il existe des algorithmes linéaires pour ce problème.La confiance n'exclut pas le contrôle
Plus précisément, si f=fib-rec(n), alors le nombre d'appels que tu fais peut aller jusqu'à (1+√5)×f, ce qui signifie que tu fais f additions +1 et √5×f additions +0 totalement inutiles.
Mais il existe des algorithmes linéaires pour ce problème.La confiance n'exclut pas le contrôle