Université Mohammed V de Rabat
Faculté des Sciences
Département Informatique
Programmation C 2
TC Informatique Appliquée S2
TP4 : La complexité
Objectifs :
• Implémenter plusieurs algorithmes de complexités différentes pour un même problème.
• Mesurer leur temps d'exécution.
• Comparer empiriquement leur efficacité.
Exercice : Recherche du Maximum dans un Tableau
Partie 1 : Implémentation des algorithmes
Tapez les trois programmes ci-dessous écrits en C pour trouver le maximum dans un tableau
d'entiers, puis s’assurez de la complexité de chacune des trois approches :
1. Approche naïve (O(n²)) : Consiste à comparer chaque élément avec tous les autres pour
vérifier s'il est le maximum.
int max_naif(int *tab, int n) {
int i, j, max, est_max;
for (i = 0; i < n; i++) {
est_max = 1; // Supposons que tab[i] est le max
for (j = 0; j < n; j++) {
if (tab[j] > tab[i]) {
est_max = 0; // tab[i] n'est pas le max
break;
}
}
if (est_max) return tab[i];
}
return -1; // Cas où le tableau est vide
}
2. Approche optimale (O(n)) : consiste à parcourir le tableau une seule fois pour trouver
le max.
int max_optimise(int *tab, int n) {
if (n == 0) return -1;
int max = tab[0];
for (int i = 1; i < n; i++) {
if (tab[i] > max) max = tab[i];
}
return max;
}
1/2
Université Mohammed V de Rabat
Faculté des Sciences
Département Informatique
Programmation C 2
TC Informatique Appliquée S2
3. Approche récursive (O(n) mais avec overhead) : consiste à utiliser la récursivité pour
diviser le problème.
int max_recursif(int *tab, int n) {
if (n == 1) return tab[0]; // Cas de base : un seul élément.
int max_restant = max_recursif(tab + 1, n - 1); // Max du sous-tableau (récursion).
if (tab[0] > max_restant) {
return tab[0];
} else {
return max_restant;
}
}
Partie 2 : Mesure du temps d'exécution
Nous allons utiliser la fonction clock() de <time.h> pour mesurer le temps d'exécution de chaque
fonction sur un grand tableau (rempli aléatoirement). Cette fonction renvoie le temps processeur
utilisé depuis le début du programme courant.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void tester_performance(int (*fonction)(int*, int), int *tab, int n, char *nom) {
clock_t debut = clock();
int max = fonction(tab, n);
clock_t fin = clock();
double temps = (double)(fin - debut) / CLOCKS_PER_SEC;
printf("%s : Max = %d, Temps = %f sec\n", nom, max, temps);
}
int main() {
int n = 10000; // Testez avec différentes tailles
int *tab = malloc(n * sizeof(int));
srand(time(NULL));
for (int i = 0; i < n; i++) tab[i] = rand() % 100000;
tester_performance(max_naif, tab, n, "Naif O(n²)");
tester_performance(max_optimise, tab, n, "Optimise O(n)");
tester_performance(max_recursif, tab, n, "Recursif O(n)");
free(tab);
return 0;
}
Partie 3 : Analyse des résultats
1. Exécutez le programme avec différentes tailles de tableau (ex : n = 1000, 10000, 100000).
2. Notez les temps d'exécution et vérifiez qu'ils correspondent aux complexités théoriques.
3. Pourquoi l'approche naïve est-elle si lente ?
4. Pourquoi la récursivité peut être moins efficace malgré sa complexité théorique en O(n)?
2/2
Université Mohammed V de Rabat
Faculté des Sciences
Département Informatique
Programmation C 2
TC Informatique Appliquée S2
5. Quel est l'impact de la taille des données sur le temps d'exécution ?
3/2