TD : Complexité des algorithmes
Exercice 1
On considère deux manières de représenter ce que l’on appelle des « matrices creuses », c'est-
à-dire des matrices d’entiers contenant environ 90% d’éléments nuls :
a) La matrice est représentée par un tableau à deux dimensions dont les cases
contiennent les éléments.
b) La matrice est représentée par un tableau à une dimension. On ne s’intéresse
qu’aux éléments de la matrice qui ne sont pas nuls. Chaque case du tableau
contient un triplet (i, j, a) correspondant à l’indice de ligne, l’indice de colonne, et
la valeur d’un élément non nul.
Le problème considéré consiste à calculer la somme des éléments d’une matrice. On
demande d’écrire un algorithme permettant de calculer cette somme, pour chacune des deux
représentations, puis de comparer leur complexité spatiale (espace mémoire occupé) et leur
complexité temporelle (nombre d’opérations à effectuer). Que peut-on conclure de cette
comparaison ? Montrer qu’il existe une valeur critique du nombre d’éléments non nuls à partir
de laquelle une méthode l’emporte sur l’autre.
Exercice 2
On considère, pour effectuer la recherche d’un élément dans un tableau, la recherche
séquentielle et la recherche dichotomique. On s’intéresse à leur complexité temporelle.
Pour cela, considérer un tableau ayant mille éléments (version trié, et version non trié). Pour
chaque algorithme, et pour chaque version du tableau, combien de comparaisons sont à
effectuer pour :
- trouver un élément qui y figure ?
- trouver un élément qui n'y figure pas ?
Quels sont les cas où le tableau est parcouru complètement et les cas où un parcours partiel
est suffisant ?
Conclure en donnant la complexité temporelle pour chaque algorithme
Exercice 3
On considère un tableau à une dimension contenant des lettres majuscules. On désire
compter la fréquence de chacune des 26 lettres de l’alphabet. Ecrire deux procédures qui
donnent en sortie un tableau de fréquence: l’une où le tableau est parcouru 26 fois, et l’autre
(plus performante !) où le calcul est fait en un seul parcours. On pourra supposer que l’on
dispose d’une fonction auxiliaire position(lettre) qui pour chaque lettre donne sa position dans
l’alphabet : position(‘A’) = 1, …, position(‘Z) = 26.
Exercice 4
On considère trois tris élémentaires : le tri sélection, le tri par insertion (trois variantes), et le
tri bulle. On considère pour un tableau les deux cas extrêmes où le tableau est déjà trié (dans
l’ordre croissant), et celui où il est trié dans l’ordre décroissant. Décrire avec précision le
comportement et la complexité de chacun des algorithmes dans ces deux cas. Quelles
conséquences peut-on en tirer ?