Complexité temporelle

lolita-01 Messages postés 90 Date d'inscription Statut Membre Dernière intervention -
KX Messages postés 16760 Date d'inscription Statut Modérateur Dernière intervention - 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:

1 réponse

Réponse 1 / 1

KX Messages postés 16760 Date d'inscription Statut Modérateur Dernière intervention 3 020

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

restrictions de compte

Restriction Pour Utilisateurs

restriction istrateur système

Impossible de modifier mot de e

Votre réponse

Discussions similaires