Forum des informaticiens de la FST
L'équipe du Forum Info-Fst, vous souhaite la bienvenue parmi nous.

calcule de la complexité de cet algorithme

Aller en bas

calcule de la complexité de cet algorithme

Message par BOMBA le Ven 15 Jan - 10:31

Bonjour,

J'ai un algorithme qui contient des boucles for , des structures conditionnelles if... else ...
des appels à des fonctions, de lecture et des écritures.

La question qui se pose comment calculer la complexité de cet algorithme ?


Merci.
avatar
BOMBA
habitué(e)
habitué(e)

Masculin Nombre de messages : 79
Age : 34
Section et Année : TIC
Date d'inscription : 07/11/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: calcule de la complexité de cet algorithme

Message par Spartacus le Ven 15 Jan - 10:51

pour avoir une complexité il faut voir les boucles imbriqué (lés traitements intermédiaire sont négligeables par rapport au temps d'exécution des boucles) et puis tu prend le sup un exemple ? OK

Debut

for(balablaba)
for(blablabla)
//traitement
ffor
ffor
// traitement

for(balablaba)
//traitement
ffor

end;

C(n) = n^2+n on dit que C= O(n^2)
avatar
Spartacus
Membre fidèle
Membre fidèle

Masculin Nombre de messages : 144
Age : 89
Section et Année : Gladiateur
Localisation : Colisée de rome
Date d'inscription : 18/10/2008

Voir le profil de l'utilisateur http://fr.wikipedia.org/wiki/Spartacus

Revenir en haut Aller en bas

Re: calcule de la complexité de cet algorithme

Message par BOMBA le Dim 17 Jan - 0:59

Bonjour,

Quelle est la complexité au pire de cas pour le calcul de toutes les combinaisons possibles pour n caractères ?

Prenons par exemple 4 caractères:a, b, c et d

Toutes les combinaisons possibles sont:
- les combinaisons de taille 1 sont: a, b, c, d //ici on a 4 combinaisons
- les combinaisons de taille 2 sont: ab, ac, ad, bc, bd, cd //ici on a 6 combinaisons
- les combinaisons de taille 3 sont: abc, abd, acd, bcd //ici on a 4 combinaisons
- les combinaisons de taille 4 sont: abcd //ici on a 1 combinaison


Merci.
avatar
BOMBA
habitué(e)
habitué(e)

Masculin Nombre de messages : 79
Age : 34
Section et Année : TIC
Date d'inscription : 07/11/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: calcule de la complexité de cet algorithme

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum