Calculer la complexité d'un algorithme

Signaler
Messages postés
23
Date d'inscription
jeudi 11 juin 2020
Statut
Membre
Dernière intervention
7 juillet 2021
-
Messages postés
8
Date d'inscription
lundi 30 novembre 2020
Statut
Membre
Dernière intervention
9 juillet 2021
-
Bonjour,
j'ai coder un algorithme récursif qui calcule le nième terme de la suite
suivante
U(0)=0
U(1)=1
U(n)=U(n-2)+U(n-1) pour n > 1
ma solution est :
#include<stdlib.h>
#include<stdio.h>
int u(int n){
int y;
if(n==0) return 0;
if(n==1) return 1;
if(n>1){
y=u(n-2)+u(n-1);
}
return y;
}
int main(){

printf("%d",u(5));
return 0;
}

Mais je n'arrive pas a montrer par récurrence que la complexité de cette solution pour calculer U(n) est en ordre de (1+√5)/2)^n.
Svp, comment puis -je répondre a cette questione.
Merci d'avance




Configuration: Windows / Chrome 91.0.4472.124

2 réponses

Messages postés
16462
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
1 août 2021
883
J'ai essayé de calculer la complexité, mais je ne sais pas comment le faire ,lorsque on a une fonction récursive, car c est pas le même lorsque on a une fonction itérative. tous ce que je sais c'est il faut le montrer en utilisant la récurrence.
NB:
Je n'attends pas que vous fassiez les exos à ma place, j'attends une explication, un tuto ou une aide pour que je puisse le faire moi-même.
MERCI POUR VOTRE RÉPONSE
Messages postés
16462
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
1 août 2021
883 > LACHHABFADOUA
Difficile de t'aider sans connaitre ton contexte.

Peut-être: http://math.univ-lyon1.fr/irem/IMG/pdf/04_Complexite.pdf
Messages postés
8
Date d'inscription
lundi 30 novembre 2020
Statut
Membre
Dernière intervention
9 juillet 2021
2
Bonjour,
on reconnaît un algorithme pour calculer les nombres de la suite de Fibonacci. Le lien qu'à yg_be te donne une idée de résolution.
Mais qu'est-ce qui te bloque avec la récursivité ?