Calculer la complexité d'un algorithme

Fermé

LACHHABFADOUA Messages postés 23 Date d'inscription jeudi 11 juin 2020 Statut Membre Dernière intervention 7 juillet 2021 - 7 juil. 2021 à 22:25
wytekrow Messages postés 8 Date d'inscription lundi 30 novembre 2020 Statut Membre Dernière intervention 9 juillet 2021 - 9 juil. 2021 à 01:05

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

A voir également:

Calculer la complexité d'un algorithme
Comment calculer la moyenne sur excel - Guide
Logiciel algorithme gratuit - Télécharger - Édition & Programmation
Ecrire un algorithme qui permet de calculer la somme de deux nombres - Forum Programmation
Calculer alimentation pc - Guide
Rolland souhaite calculer le montant total des ventes de son magasin. le fichier contient, pour chaque produit, la quantité vendue et le prix unitaire. calculez le montant total des ventes. ✓ - Forum Excel

2 réponses

Réponse 1 / 2

yg_be Messages postés 22720 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 23 avril 2024 1 476
8 juil. 2021 à 11:18

bonjour,
qu'as-tu essayé?
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/

LACHHABFADOUA
Modifié le 8 juil. 2021 à 15:36

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

yg_be Messages postés 22720 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 23 avril 2024 1 476 > LACHHABFADOUA
8 juil. 2021 à 15:55

Difficile de t'aider sans connaitre ton contexte.

Peut-être: http://math.univ-lyon1.fr/irem/IMG/pdf/04_Complexite.pdf

Réponse 2 / 2

wytekrow Messages postés 8 Date d'inscription lundi 30 novembre 2020 Statut Membre Dernière intervention 9 juillet 2021 2
9 juil. 2021 à 01:05

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é ?

Discussions similaires

Convertir une note sur 20 .

exo pix

algorithme résoudre ax²+bx+c=0

je veut créer des codes

Comment transformer une note sur 20

Discussions similaires

Newsletters