Bonjour,
Mon sujet ne parle pas à proprement parlé de mathématiques mais plus de calcul d'un algorithme (je ne sais donc pas si je le place dans le bon forum ou non, si ce n'est pas le cas j'en suis désolé), avec l'utilisation d'équations récurrentes.
On me demande d'exprimer la complexité C(n) pour n impair, sous forme d'une équation de récurrence, puis d'en déduire l'expression de C(n) en fonction de n.
Seule la comparaison sera considéré comme opération significative sur les test de n.
Voici l'algorithme :
Algorithme : fonction f
début
/*Entrées : un entier naturel n */
/* Sortie : f(n) */
si n≤2 alors retourner 1
sinon
si n pair alors retourner f(n-2)+f(n-4)
sinon retourner n*f(n-2)
Complexité C(n) = 2 + C(n-2) (ça j'ai compris pourquoi, 2 test sur n et on rappel f à dimension n-2)
C'est la suite que je ne comprends quand la correction déroule :
C(n) = 2 + C(n-2)
C(n-2) = 2 + C(n-4) // le test sur n reste à deux car ces 2 comparaison ne sont pas récursives
...
C(3) = 2 + C(1) // pourquoi le calcul de la complexité s'arrête à C(3) ?
C(n) = 2 * ((n-1)/2) + C(1) // comment cette formule est-elle obtenue ? Car je ne vois aucun lien entre la ligne du haut et celle ci
= n-1+1 // pourquoi C(1) = 1 ?
merci d'avance pour vos réponses
-----