Scribd
Importer
11 vues3 pages

Complexité des Algorithmes et Fonctions

Le document présente une série d'exercices sur la complexité algorithmique, demandant de calculer la complexité de diverses procédures et fonctions. Les exercices incluent des opérations de base comme l'échange de valeurs, le calcul de maximum, de somme, et des algorithmes de tri comme le tri à bulles et l'insertion. Chaque exercice nécessite une analyse de la complexité en fonction de la taille des entrées.

Transféré par

ScribdTranslations
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
11 vues3 pages

Complexité des Algorithmes et Fonctions

Le document présente une série d'exercices sur la complexité algorithmique, demandant de calculer la complexité de diverses procédures et fonctions. Les exercices incluent des opérations de base comme l'échange de valeurs, le calcul de maximum, de somme, et des algorithmes de tri comme le tri à bulles et l'insertion. Chaque exercice nécessite une analyse de la complexité en fonction de la taille des entrées.

Transféré par

ScribdTranslations
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

EXERCICES DE COMPLEXITÉ ALGORITHMIQUE

1. Calculez la complexité de la procédure suivante :

PROCÉDURE échange(REF x : ENTIER, REF y : ENTIER) EST


aux : ENTERO;
aux := x;
x := y;
y := aux;
FINPROCÉDURE

2. Calculer la complexité de la fonction suivante :

FONCTION max(x : ENTIER, y : ENTIER) : ENTIER EST

ENTIER
SI (x >= y) ENTONCES
x;
SINO
résultat := y;
FINSI
RENVOYER résultat;
FINFONCTION

3. Calculer la complexité de la fonction suivante :

FONCTION somme (v : VECTEUR(ENTIER), taille : ENTIER) : ENTIER EST


ENTIER; résultat := 0;
POUR i DE 0 À taille-1 FAIRE
resultat := resultat + v[i];
FINPARA
RENVOYER résultat;
FINFUNCION

4. Calculer la complexité de la fonction suivante

FONCTION aSavoir(v : VECTEUR(ENTIER), n: ENTIER) : ENTIER EST


ENTIER
resultat := 0; i := 0;
TANT QUE (i < taille) FAIRE
resultat := resultat + v[i];
i := i + 1;
FINMIENTRAS
RETOURNER résultat;
FINFUNCION

-1-
5. Calculer la complexité de la fonction suivante

FONCTION aSavoir(v : VECTEUR(ENTIER), n: ENTIER) : ENTIER EST


ENTIER
resultat := 0; i := taille - 1;
MIENTRAS (i >= 0) FAIRE
resultat := resultat + v[i];
i := i - 1;
FINMIENTRAS
RENDRE le résultat;
FINFONCTION

6. Calculer la complexité de la fonction suivante

FONCTION aSavoir(v : VECTEUR(ENTIER), n : ENTIER) : ENTIER EST


ENTIER
result := 0; i := tamaño - 1;
TANT QUE (i >= 0) FAIRE
resultat := resultat + v[i];
i := i - 2;
FINMIENTRAS
RENVOYER le résultat;
FINFONCTION

7. Calculer la complexité de la fonction suivante

FONCTION aSavoir(v : VECTEUR(ENTIER), n: ENTIER) : ENTIER EST


ENTRÉE
0
TANT QUE ((i < taille) && ((v[i] DIV 2) != 0) FAIRE
resultat := resultat + v[i];
i := i + 1;
FINMIENTRAS
RENVOYER résultat;
FINFUNCION

8. Calculer la complexité de la fonction suivante

FONCTION aSavoir(v : VECTEUR(ENTIER), n: ENTIER) : ENTIER EST


ENTIER
result := 0; i :=0;
TANT QUE (i < taille-1) FAIRE
SI (v[i] <= v[i+1]) ENTONCAS
intercambia(v[i],v[i+1]);
FINSI
FINMIENTRAS
RENVOYER le résultat;
FINFUNCION

NOTA : intercambia est la fonction de l'exercice 1

-2-
9. Calculer la complexité de la procédure suivante

PROCÉDURE bulle(v : VECTEUR(ENTIER), taille : NATUREL) EST


i, j : ENTIER;
POUR i DEPUIS 2 JUSQU'À taille - 1 FAIRE
POUR j DE 0 À taille – i FAIRE
SI (v[j] > v[j+1]) ENTONNES
intercambia(v[j],v[j+1]);
FINSI
FINPARA
FINPARA
FINPROCÉDURE

10. Calculer la complexité de la procédure suivante.

PROCÉDURE insertion(v : VECTEUR(INTEGER), taille : NATUREL) EST


i, j : ENTIER;
POUR i DE 0 À taille - 2 FAIRE
min : ENTIER; min := i;
POUR j DE i+1 À taille - 1 FAIRE
SI (v[j] < v[min]) ALORS
min := j;
FINSI
FINPARA
interchange(v[i],v[min])
FINPARA
FINPROCEDURE

11. Calculer la complexité de la procédure suivante.

PROCÉDURE insertion(v : VECTEUR(ENTIER), taille : NATUREL) EST


i, j : ENTIER;
POUR i DE 0 À taille - 2 FAIRE
intercambia(v[i],v[posMinimo(v,i,tamaño-1)])
FINPARA
FINPROCÉDURE

FONCTION posMinimo(v : VECTEUR(ENTIER), debut, fin : NATUREL) EST


ENTIER
resultat := debut;
POUR et DEPUIS début+1 JUSQU'À fin FAIRE
SI (v[i] < v[min]) ALORS
resultat := i;
FINSI
FINPARA
RENVOYER le résultat;
FINFUNCION

-3-

Vous aimerez peut-être aussi