Complexité temporelle

Fermé

lolita-01 Messages postés 90 Date d'inscription mercredi 5 janvier 2011 Statut Membre Dernière intervention 26 juillet 2013 - 18 nov. 2012 à 21:10
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 18 nov. 2012 à 21:16

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

A voir également:

Complexité temporelle
Une restriction de compte d'utilisateur (ex. une restriction temporelle) - Forum Windows
Sécurité bureau a distance - Forum Windows serveur
RDP et restriction utilisateurs - Forum Windows
Complexité - Forum VB / VBA
Complexité ✓ - Forum Programmation

1 réponse

Réponse 1 / 1

KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
Modifié par KX le 18/11/2012 à 21:38

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

Discussions similaires

[Bureau a distance] limitation des compte

Impossible de modifier mot de passe

restrictions de compte

Restriction Pour Utilisateurs

comment avoir de la poudre temporelle