Calculer la complexité d'un algorithme
LACHHABFADOUA
Messages postés
24
Statut
Membre
-
wytekrow Messages postés 8 Statut Membre -
wytekrow Messages postés 8 Statut Membre -
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
A voir également:
- Calculer la complexité d'un algorithme
- Comment calculer la moyenne sur excel - Guide
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Comment calculer un total sur excel - Guide
- Barbara veut calculer automatiquement son budget dans un tableau. citez un des logiciels lui permettant de faire des calculs sur des tableaux de nombres (tableur). - Forum Excel
- Calculer un acompte de 40 ✓ - Forum Windows
2 réponses
yg_be
Messages postés
24281
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 585
bonjour,
qu'as-tu essayé?
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/
qu'as-tu essayé?
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/
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
Peut-être: http://math.univ-lyon1.fr/irem/IMG/pdf/04_Complexite.pdf