Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Conception de structures de données

Cours 2 Rappels sur la complexité

Algorithmes et complexité

25 février 2013

Struct 1/23 Struct 2/23

Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Mesurer l’efficacité d’un algorithme Quel est le paramètre ?

Le temps d’exécution d’un programme dépend : Première chose à faire : évaluer la TAILLE DES DONNÉES,
des données du problème pour cette exécution c’est-à-dire les entrées (instances) manipulées par l’algorithme.
de la qualité du code engendré par le compilateur
On doit essayer de choisir comme taille ( la ou ) les
de la nature et de la rapidité des instructions du processeur dimensions les plus significatives.
de l’efficacité de l’algorithme Par exemple, selon que le problème est modélisé par :
de l’encodage des données des nombres : les valeurs de ces nombres, le nombre de
chiffres dans leur codage binaire, ...
... et aussi de la qualité de la programmation !
des polynômes : le degré, le nombre de coefficients 6= 0, ...
Pour mesurer l’efficacité d’un algorithme : des matrices m × n : max(m, n), m.n, m + n, ...
des arbres : la hauteur, le nombre de noeuds, de feuilles, ...
On oublie ce qui est subjectif (programmeur, matériel, ... ). des listes, tableaux, fichiers : nombre de cases, d’éléments, ...
On cherche une grandeur n pour “quantifier” les entrées. des mots : leur longueur, le nombre de lettres de l’alphabet
utilisé pour les écrire, ...
On calcule les performances uniquement en fonction de n.
! ! Le choix d’un structure de données à une grande
B complexité d’un ALGORITHME, pas d’un programme ! influence sur l’efficacité d’un algorithme ! !

Struct 3/23 Struct 4/23

Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Qu’est ce que l’on compte ? Il n’y a pas que la taille qui compte...
Un algo ne sert pas à résoudre 1 seule instance d’un problème !
Dans l’idéal, il faut compter toutes les “opérations”
B exemple d’un algo de recherche d’élément dans un tableau trié.
élémentaires impliquées dans l’algorithme.
Or, on sait (cours d’Archi) que toutes les instructions n’ont La taille du problème : le nombre de cases du tableau.
pas le même coût en temps ! Le temps de la recherche dépend de l’algorithme choisi, mais
Il faut choisir quelles opérations compter : des opérations aussi des paramètres (le tableau et l’élément à trouver).
Exemples :
simples et indépendantes de l’implantation de l’algorithme.
Recherche séquentielle :
C’est la nature du problème qui rend certaines opérations
e ... meilleur cas
plus fondamentales que d’autres dans un algorithme. 0 n-1
Avec un peu d’habitude, on les repère : ... e pire cas
Recherche d’un élément dans un tableau, une liste, un arbre 0 n-1
Recherche dichotomique :
Tri d’une liste, d’un tableau, d’un fichier e ... pire cas
0 n-1

Multiplication de polynômes, de matrices, de grands entiers ... e ... meilleur cas

0 n/2 n-1

Et pour simplifier, on peut faire l’hypothèse que toutes ces Il faudrait une moyenne sur toutes les instances du problème...
opérations élémentaires ont un coût uniforme. B Calcul de la complexité d’un algo dans le PIRE cas !
Struct 5/23 Struct 6/23
Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Complexité asymptotique La notation O

Ce n’est pas très intéressant d’étudier la complexité si la taille Definition

du problème est petite : Pour une fonction g(n) donnée, on note O(g(n)) l’ensemble de
B L’efficacité d’un algorithme n’est un enjeu important que sur fonctions suivant :
les gros problèmes. O(g(n)) = { f (n) | ∃c et n0 , ∀n ≥ n0 , 0 ≤ f (n) ≤ c · g(n) }
On ne sait pas où est la limite entre petits et gros problème...
On note f (n) = O(g(n)) et on dit “en grand O de g(n)”.
C’est pourquoi on regarde la complexité asymptotique des algos.
B Asymptotique : quand la taille n du problème tend vers ∞.
exemple : il n’est pas vrai que pour tout n ≥ 0, n2 ≥ 10 000 n, c.g(n) Exemples
mais asymptotiquement, n2 est plus grand que 10 000 n. f(n) 1 000 000 = O(1)
Il n’est pas toujours évident de compter exactement le nombre n = O(n)
d’opérations impliquées dans les algorithmes. 10n = O(n2 )
B On se contente de trouver des approximations.
99n + 2100 = O(n)
B En général on majore la complexité :
c’est-à-dire que l’on donne une borne supérieure (une borne 5n3 + 50n2 + 8 = O(n3 )
n
que l’on est sûr de ne jamais dépasser). 0 n0 n10 = O(2n )
Struct 7/23 Struct 8/23
Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Propriétés utiles Quelques classes de complexité

Pour toute constante c > 0 et toutes fonctions g, g1 , g2 : constant O(1) • opérations élémentaires :
c = O(1) affectation, comparaison, ...
B 210 = O(1), toute opération qui ne dépend pas de n... logarithmique O(log n) • recherche dichotomique



c · O g(n) = O g(n) linéaire O(n) • recherche séquentielle
B 3n = O(n), boucle de longueur n avec 3 affectations... • recherche du max (ou min)



• calculer la longueur d’une liste
O g(n) + O g(n) = O g(n)
B n + n + · · · + n = O(n), quasi-linéaire O(n log n) • tri fusion
plusieurs boucles de longueur n qui se suivent... quadratique O(n2 ) • tri à bulle, tri par insertion




O g1 (n) + O g2 (n) = O max(g1 (n), g2 (n)) • parcours d’une matrice n × n
B n2 + n = O(n2 ), • recherche de motif dans
initialiser la 1e ligne d’une matrice puis tout le reste une chaı̂ne de caractères




O g1 (n) · O g2 (n) = O g1 (n) · g2 (n) polynomial O(nk ) avec k fixé (k = 3 : cubique)
B n · n = O(n2 ), 2 boucles imbriquées de longueur n exponentiel O(k n ) • Fibonacci récursif

Struct 9/23 Struct 10/23

Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Synthèse

Déterminer la TAILLE n du problème.

Choisir les OPÉRATIONS à compter.
Déterminer quel est le PIRE CAS pour l’algorithme. Choisir un tableau
B Ne pas oublier que n est grand.
comme structure de données
COMPTER (APPROXIMATIVEMENT) le nombre
d’opérations élémentaires en fonction de n.
→ donner une borne supérieure la plus précise possible.

B Pour tous les algos étudiés : donner la complexité !

Struct 11/23 Struct 12/23

Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Choix d’une structure de données Opérations sur un tableau non trié

B Tableau tab non trié de taille (variable) n :
Comment modéliser... accès au ie élément
recherche de l’élément e
... un ensemble (une collection) d’entiers ? insertion de l’élément e
suppression de l’élément e
... une file d’attente pour une imprimante ? suppression de l’élément d’indice i

... une liste d’étudiants ?

... un dictionnaire (T9) de téléphone portable ?

...

Struct 13/23 Struct 14/23

Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Opérations sur un tableau préservant l’ordre Opérations sur un tableau trié

B Tableau tab non trié de taille n dans lequel l’ordre relatif des
éléments doit être préservé : mêmes complexités, sauf pour B Tableau tab trié de taille (variable) n :
la suppression : O(n) dans tous les cas ! accès au ie élément
recherche de l’élément e
Dans le cas de la file d’attente, 2 possibilités :
0 n-1 TMAX insertion d’un élément e ?

insertion (en fin)

suppression (en tête)
0 deb fin = deb + n -1 TMAX

insertion (en fin) suppression de l’élément e

suppression (en tête) suppression de l’élément d’indice i
nombre d’insertions borné !
Struct 15/23 Struct 16/23
Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Recherche dichotomique Algorithmes de TRI

int rechercheDicho(int elem, int tab[], int lg){ TRI : étant donnés un ensemble de données et une relation
int debut = 0; d’ordre sur ces données, les trier en ordre croissant.
int fin = lg-1; les données peuvent être des entiers, des flottants ( !), des
int milieu = (debut+fin)/2; mots, des structures complexes, ...
while(debut<=fin) elles peuvent être dans un tableau, une liste, un fichier, ...
if (elem == tab[milieu]) l’ordre peut être numérique, lexicographique, militaire, ...
return milieu; Algorithmes de tri :
else if (elem < tab[milieu]){ les LENTS :
fin = milieu-1; /* cherche à gauche... */ tri par insertion
milieu = (debut+fin)/2; tri à bulles
} tri par sélection
...
else{ debut = milieu+1; /* elem > tab[milieu] */
les RAPIDES :
milieu = (debut+fin)/2; /* ... à droite */
tri par fusion (pas en place)
} tri rapide (quicksort) : rapide en moyenne
return -1; /* si on n’a rien trouvé dans le while */ tri par tas (structure de données complexes)
} ...
Struct 17/23 Struct 18/23
Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Tri par INSERTION Principe du tri par SÉLECTION (prog. en TD)

Principe : Séparer le tableau en 2 parties :
Séparer le tableau en une partie triée et l’autre non ; la 1ère est triée et contient les + petits éléments du tableau ;
Au début, la partie triée est vide ; la seconde n’est pas triée et contient des éléments + grands
À chaque étape, on insère le premier élément de la partie que tous ceux de la 1ère partie ;
non triée dans la première partie du tableau, de sorte que Au début, la partie triée est vide ;
celle-ci reste triée. À chaque étape, on sélectionne le plus petit élément de la
partie triée partie non triée est on l’insère à la fin de la partie triée.
0 i n-1
0 i Min n-1

partie triée

0 i+1 n-1 0 i+1 n-1

partie triée partie triée

Complexité ? ? Complexité ? ?
Struct 19/23 Struct 20/23
Complexité Algos sur les tableaux Complexité Algos sur les tableaux

Quicksort Tri Fusion

pivot
0 n/2 n-1
0 n/2 n-1

5 1 11 3 12 7 10 8 4 2 9 6 5 1 11 3 12 7 10 8 4 2 9 6
séparer
séparer
<= pivot >pivot

1 3 4 2 5 11 12 7 10 8 9 6 5 1 11 3 12 7 10 8 4 2 9 6
trier récursivement trier récursivement
trier récursivement trier récursivement

1 3 5 7 11 12 2 4 6 8 9 10
1 2 3 4 5 7 6 8 9 10 11 12
fusionner
fusionner

1 2 3 4 5 6 7 8 9 10 11 12

Complexité ? Complexité ?

Struct 21/23 Struct 22/23

Complexité Algos sur les tableaux

Synthèse des opérations sur les tableaux

tableau tableau tableau

Opération non trié ordonné trié
Accès au ie élément O(1) O(1) O(1)
Insertion d’un élément e O(1) O(1) O(n)
Suppression d’un élément e O(n) O(n) O(n)
Suppression du ie élément O(1) O(n) O(n)
Recherche d’un élément e O(n) O(n) O(log n)
Tri O(n log n) – –

Conclusion : il faut choisir une structure de données

adaptée au problème que l’on doit résoudre.

Struct 23/23