Calculer la complexité d'un algorithme
LACHHABFADOUA
Messages postés
24
Statut
Membre
-
wytekrow -
wytekrow -
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 :
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
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
-
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
bonjour,
qu'as-tu essayé?
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/-
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- Difficile de t'aider sans connaitre ton contexte.
Peut-être: http://math.univ-lyon1.fr/irem/IMG/pdf/04_Complexite.pdf
-
-
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é ?
