Master Informatique : Sécurité et Technologie Web
Matière : Algorithmique avancée et complexité
Universitaire Abbès Laghrour Khenchela
Faculté des Sciences et de la Technologie
Département MI
TD 1 : Complexité algorithmique : Rappel
Exercice 1 :
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 2 :
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.
Quelle est la complexité des deux procédures ?
Exercice 3 :
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 ?
Dr Hemam Sofiane 1
Master Informatique : Sécurité et Technologie Web
Matière : Algorithmique avancée et complexité
Corrigé TD 1
Exercice 1 :
Opérations élémentaires retenues: les comparaisons
1. Recherche séquentielle dans un tableau de 1000 éléments non trié
élément ne s’y trouvant pas (complexité au pire) : 1000 comparaisons ( tableau est
parcouru complètement)
élément qui s’y trouve (complexité moyenne) : n/2=500 comparaisons (parcours
partiel suffisant)
algorithme en O(n)
2. Recherche séquentielle dans un tableau trié
élément ne s’y trouvant pas (complexité au pire) : 1000 comparaisons (parcours
partiel suffisant)
élément qui s’y trouve (complexité moyenne) : n/2=500 comparaisons (parcours
partiel suffisant)
algorithme en O(n)
3. Recherche dichotomique (dans un tableau non trié) : impossible
4. Recherche dichotomique (dans un tableau trié)
complexité au pire = complexité moyenne = nombre p d'intervalles considérés
Exemple avec n = 8= 23 tableau de 8 éléments 3 comparaisons
Niveau 0
Niveau 1
Niveau 2
Niveau 3
Profondeur de l’arbre
de décision :
de l’ordre de log 2n
Donc pour un tableau
de 1000 éléments,
disons 1024 10 comparaisons
algorithme en O(log2n)
Dr Hemam Sofiane 2
Master Informatique : Sécurité et Technologie Web
Matière : Algorithmique avancée et complexité
Exercice 2 :
La méthode qui parcourt le tableau 26 fois consiste à parcourir le texte pour compter d’abord
tous les A, recommencer pour compter tous les B, etc. On utilise un tableau d’entiers de 26
cases, qui sert à mémoriser les occurrences.
La deuxième méthode demande de disposer de la conversion d’une lettre en un entier, qui
correspond à sa place dans l’alphabet. (En c++, on ferait tout simplement appel à i = car –
‘A’).
char texte[TMAX]
int cpt, pos, occ[26]
pour cpt := 1 à 26 faire
occ[cpt]:= 0 {initialisation à zéro}
fin pour
cpt := 1
tant que(texte[cpt] ≠CARFIN) faire
pos := conversion(texte[cpt])
occ[pos] := occ[pos] + 1
cpt := cpt + 1
fin tant que
Exercice 3 :
Le tri sélection fait autant de comparaisons dans tous les cas. La seule différence tient au
nombre de mises à jour du minimum.
Ce tri a cependant l’avantage de ne faire que peu d’échanges, ce qui peut être important pour
des données de grande taille.
Le tri par insertion sous la dernière variante donnée en cours ne fait qu’un test par tour de
boucle si le tableau est trié, d’où une complexité linéaire dans ce cas : avantage pour les
tableaux presque triés.
Pour le tri bulle, le comportement dépend du fait que l’on ait ou pas modifié l’algorithme pour
qu’il s’aperçoive qu’un
tableau est trié (ce qui est le cas si aucune permutation n’a été faite au cours d’une passe)
Dr Hemam Sofiane 3