Calculer la complexité d'un algorithme

LACHHABFADOUA Messages postés 23 Date d'inscription   Statut Membre Dernière intervention   -  
wytekrow Messages postés 8 Date d'inscription   Statut Membre Dernière intervention   -
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

Réponse 1 / 2
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
bonjour,
qu'as-tu essayé?
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/
0
LACHHABFADOUA
 
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
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > LACHHABFADOUA
 
Difficile de t'aider sans connaitre ton contexte.

Peut-être: http://math.univ-lyon1.fr/irem/IMG/pdf/04_Complexite.pdf
0
Réponse 2 / 2
wytekrow Messages postés 8 Date d'inscription   Statut Membre Dernière intervention   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é ?
0

Discussions similaires

Calcul des ventes par mois d'un produit
buck.danny -
elena -

7 réponses
Un algorithme sur excel ou un logiciel à programmer
Lafille -
Raymond PENTIER -

3 réponses
algorithme résoudre ax²+bx+c=0
enimarix -
Utilisateur anonyme -

1 réponse
exo pix
Xtyller -
Raymond PENTIER -

2 réponses
Comment mettre ma note sur 20
Manonv6 -
xplom -

5 réponses