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
Algorithme qui calcule le carré d'un nombre - Forum Algorithmes / Méthodes
Logiciel algorithme gratuit - Télécharger - Édition & Programmation
Comment calculer la somme sur excel - Guide
Comment calculer une note sur 20 ✓ - Forum Bureautique

2 réponses

Réponse 1 / 2

yg_be Messages postés 23421 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 janvier 2025 Ambassadeur 1 557
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 23421 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 janvier 2025 1 557 > 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

Générer toutes combinaisons possibles Euromillions dans Excel

je veut créer des codes

Calcul des ventes par mois d'un produit

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

CALCULS