Cours algorithmes et complexité

Algorithmes et complexité

Traitement des collections

• Origine des collections ¨ 1, 2, … plusieurs
Ø monôme, binôme, … polynôme
Ø point, segment, triangle, … polygone ¨ regroupe plusieurs données de même nature
• Traitements ¨ systématiques, itératifs ou récursifs
Ø affichage
Ø saisie
Ø recherche d’éléments
¨ Si ordre sur les éléments : classement, tri
¨ Efficaces jusqu’à quelles tailles de collections ?

Structures collectives étudiées

• Tables
¨ tableaux (array en Pascal) améliorés
¨ tri par insertion : nombreux décalages
¨ si le tableau est trié, recherche efficace (dichotomie)
• Listes chaînées
¨ pour des insertions et des suppressions efficaces
¨ recherche dans une liste : peu efficace
¨ tri d’une liste par fusion
• Arbres binaires de recherche (ABR)
¨ pour une recherche efficace
¨ structure maintenue triée sur ajouts et suppressions

Complexité d’un algorithme

• Pour mesurer l’efficacité d’un algorithme, pour comparer des algorithmes
¨ coût en nombre d’opérations, en fonction du nombre n de données (mots mémoire ou bits) à traiter
¨ algorithme polynomial : O(n 2) , O(n 3), … opérations
Ø parcours d’une matrice carrée n x n, produit de 2 matrices, …
¨ algorithme exponentiel : O(e n)
Ø inutilisable en pratique si n > N
• Coût moyen : pas facile à calculer
Ø hypothèses probabilistes sur la répartition des données
• Complexité : coût maximal, pire des cas

Complexité : premiers exemples

• Recherche dans un tableau non trié de n éléments
¨ pire des cas : élément cherché absent du tableau
¨ complexité linéaire : O(n) tests
• Tri naïf d’un tableau
¨ algorithme : pour chaque rang i (³ 1) dans le tableau,
Ø rechercher le maximum des éléments non triés (de i à n)
Ø échanger ce maximum avec le premier élément non trié (en i)
¨ complexité
Ø pire des cas : tableau trié à l’envers
Ø pour le rang i, la recherche coûte au plus n – i +1 tests
Ø au total, n + (n – 1) + (n – 2) + … + 1 = n (n + 1)/2 tests
Ø complexité quadratique : O(n 2), car n négligeable devant n 2
¨ naïf car il existe des tris plus efficaces

Tri d’un tableau par insertion

• Données à trier
T [1], T [2], …, T [n]
• Algorithme
Pour chaque rang i , avec 2 £ i £ n, insérer T [i] dans T [1], …, T [i – 1] supposés triés.
L’insertion s’effectue par décalages successifs.
• Complexité
Ø pire des cas : tableau trié à l’envers
Ø pour le rang i, l’insertion nécessite au pire i – 1 décalages (et une affectation)
Ø au total, 2 + 3 + … + (n – 1) + n
Ø complexité quadratique : O(n 2)
• Il existe des tris plus efficaces