Complexité
Temps de calcul
Ordres de grandeur
Comparaisons de complexités
Temps de calcul
Complexité en temps
C(A, D) = temps d’exécution de l’algorithme A appliqué
aux données D
Eléments de calcul de la complexité en temps
• C(opération élémentaire) = constant
• C(si F alors I sinon J) ≤ C(F) + max (C(I), C(J))
• C(pourtout i de e1 à e2 faire Ei) ≤
C(e1) + C(e2) + ΣC(Ei)
• Temps de calcul de procédures récursives : solution
d’équations de récurrence
2013-2014 Algorithmique 2
Temps de calcul (2)
C(A, D) dépend en général de D
Complexité au pire
CMAX (A, n) = max {C(A, D) ; D de taille n }
Complexité au mieux
CMIN (A, n) = min {C(A, D) ; D de taille n }
Complexité en moyenne
CMOY (A, n) = ΣD de taille n p(D) C(A, D)
où p(D) est la probabilité d’avoir la donnée d
CMIN (A, n) ≤ CMOY (A, n) ≤ CMAX (A, n)
2013-2014 Algorithmique 3
Exemple (complexité au pire)
Algorithme Sélection (tab, taille)
pourtout i de 1 à taille-1 faire
min ← i Cout : 1
pourtout j de i+1 à taille faire
Cout ≤ 2 +...+ 2
si tab[j] < tab[min] alors Cout ≤
(taille-i fois) =
min ← j finsi 1+1 = 2 2*(taille-i)
finpour
si i ≠ min alors
échanger(tab, i, min) finsi Cout ≤ 1+2 = 3
finpour
Cout ≤ Σi de 1 à taille-1 1+2*(taille-i) + 3
= (taille-1)*(taille+4) ~ taille2
Exemple (meilleur des cas)
Algorithme Sélection (tab, taille)
pourtout i de 1 à taille-1 faire
min ← i Cout : 1
pourtout j de i+1 à taille faire
Cout = 1 +...+ 1
si tab[j] < tab[min] alors Cout=1
(taille-i fois) =
min ← j finsi taille-i
finpour
si i ≠ min alors
échanger(tab, i, min) finsi Cout = 1
finpour
Cout ≤ Σi de 1 à taille-1 1+(taille-i) + 1
= (taille-1)*(taille+4)/2 ~ taille2
Meilleur des cas : tableau trié
1 2 3 4 5 6
1 2 3 4 5 6 1 affectation
1 2 3 4 5 6 5 comp. 0 échanges
1 2 3 4 5 6 1 affectation
1 2 3 4 5 6 4 comp. 0 échanges
1 2 3 4 5 6 1 affectation
1 2 3 4 5 6 3 comp. 0 échanges
…
A la fin : 5 affectations, 5+4+...+1 = 15 comparaisons et
0 échanges Algorithmique 6
Pire des cas : tableau trié dans
l’ordre inverse ?
6 5 4 3 2 1
6 5 4 3 2 1 1 affectation
1 5 4 3 2 6 5 comp. 1 échange
1 5 4 3 2 6 1 affectation
1 2 4 3 5 6 4 comp. 1 échange
1 2 4 3 5 6 1 affectation
1 2 3 4 5 6 3 comp. 1 échange
…
A la fin : 5 affectations, 5+4+...+1 = 15 comparaisons et
3 échanges Algorithmique 7
Pire des cas
6 1 2 3 4 5
6 1 2 3 4 5 1 affectation
1 6 2 3 4 5 5 comp. 1 échange
1 6 2 3 4 5 1 affectation
1 2 6 3 4 5 4 comp. 1 échange
1 2 6 3 4 5 1 affectation
1 2 3 6 4 5 3 comp. 1 échange
…
A la fin : 5 affectations, 5+4+...+1 = 15 comparaisons et
5 échanges Algorithmique 8
Ordres de grandeur
2n
n2
log2n
2013-2014 Algorithmique 9
Ordres de grandeur (2)
log2 n n1/2 n log2 n n2 n3 2n
n=5 ~ 2,32 ~ 2,24 ~11,6 25 125 32
n=10 ~ 3,32 ~ 3,16 ~ 33,2 100 1000 1024
n=100 ~ 6,64 10 ~ 664 10000 106 102410 ~ 1030
n=1000 ~ 9,97 ~ 31,62 ~ 9970 106 109 ~ 10300
n=10000 ~ 13,29 100 ~ 132900 108 1012 ~ 103000
2013-2014 Algorithmique 10
Ordres de grandeur (3)
Evolution quand la taille est 10 fois
Coût C(n)
plus grande : C(n × 10)
log2n C(n) + 3,32
n C(n) × 3,16
n C(n) × 10
n log2n C(n) × (10+ε)
n2 C(n) × 100
n3 C(n) × 1000
2n C(n) 10
2013-2014 Algorithmique 11
Comparaisons de complexités
Ordres de grandeur asymptotique
C(n) = O(f(n)) s’il existe une constante k > 0 et
un entier positif N tels que pour tout n ≥ N on a
C(n) ≤ k f (n)
On dit alors que C(n) est « grand O » de f (n).
Exemples :
• n = O(n2)
En effet si n ≥ 1 on a que n ≤ n2 et donc la
condition est vérifiée avec N = 1 et k = 1.
• log2n = O(nα) pour tout α > 0
• nα = O(an) pour tout α > 0 et a > 1
2013-2014 Algorithmique 12
Comparaisons de complexités
Ordres de grandeur asymptotique
C(n) = Ω(f(n)) s’il existe une constante k > 0 et
un entier positif N tels que pour tout n ≥ N on a
C(n) ≥ k f (n)
On dit alors que C(n) est « grand oméga » de f(n).
Exemples :
• Si C(n) = O(f(n)) alors f(n) = Ω(C(n))
En effet si n ≥ N on a que C(n) ≤ k f(n) avec
k > 0. Donc à partir de N on a que f(n) ≥ 1/k f(n).
2013-2014 Algorithmique 13
Comparaisons de complexités
Ordres de grandeur asymptotique
C(n) = Θ(f(n)) si
C(n) = O(f(n)) et C(n) = Ω(f(n))
On dit alors que C(n) est « grand thêta » de f(n).
Exemples :
• 2n2 + n = Θ(n2)
En effet pour n ≥ 1 on a
2n2 + n ≤ 2n2 + n2 = 3n2
et donc 2n2 + n = O(n2)
De plus, pout tout n ≥ 0 on a 2n2 + n ≥ 2n2 et
donc 2n2 + n = Ω(n2)
2013-2014 Algorithmique 14
Tris avancés
Tri fusion
Tri rapide
Le tri fusion ou Mergesort
Principe
Algorithme
Exemple
Le principe du tri fusion
Idée de base : « diviser pour régner »
Pour trier un tableau :
• On trie deux moitiés de tableau (de 1 à n/2 et
de n/2+1 à n)
• On les fusionne
On reconnaît un fonctionnement récursif
Cas d’arrêt évident : tableau à une case
2013-2014 Algorithmique 17
La fusion
On dispose de deux tableaux triés qu’on
veut fusionner
On passe par un tableau annexe qu’on va
remplir alternativement avec les éléments
des deux tableaux
• Si le premier des éléments restants du
premier tableau est inférieur au premier des
éléments restants du second, c'est lui qu'on
ajoute
• Sinon c’est l’autre
2013-2014 Algorithmique 18
La fusion (suite)
Une fois que tous les éléments ont été
traités, on a un tableau trié regroupant les
éléments des deux tableaux
• (en fait deux sous-tableaux contigus de notre
tableau de départ)
On recopie ensuite ce tableau annexe
dans le tableau de départ à la bonne place
2013-2014 Algorithmique 19
Exemple
5 4 1 2 6 3
5 4 1 2 6 3
5 4 1 2 6 3
5 4 1 2 6 3
FUSION
4 5 1 2 6 3
2013-2014 Algorithmique 20
Exemple (2)
4 5 1 2 6 3
FUSION
1 4 5 2 6 3
1 4 5 2 6 3
1 4 5 2 6 3
FUSION
1 4 5 2 6 3
2013-2014 Algorithmique 21
Exemple (3)
1 4 5 2 6 3
FUSION
1 4 5 2 3 6
FUSION
1 2 3 4 5 6
Dernière étape en détail :
On dispose de deux tableaux de 3 éléments, tous deux triés
On veut les fusionner en un seul tableau trié
On crée tout d’abord un tableau annexe vide de 6 cases
2013-2014 Algorithmique 22
Exemple (4)
1 4 5 2 3 6
1 4 5 2 3 6
Tableau auxiliaire de même taille 1
1 4 5 2 3 6
1 4 5 2 3 6
1 4 5 2 3 6
1 2
1 4 5 2 3 6
2013-2014 Algorithmique 23
Exemple (4)
1 4 5 2 3 6
1 4 5 2 3 6
1 4 5 2 3 6
1 2 3
1 4 5 2 3 6
1 4 5 2 3 6
1 4 5 2 3 6
1 2 3 4
2013-2014 Algorithmique 24
Exemple (5)
1 4 5 2 3 6
1 2 3 4
1 4 5 2 3 6
1 4 5 2 3 6
1 4 5 2 3 6
1 2 3 4 5
1 2 3 4 5 6
Tableau auxiliaire copié dans celui d’origine
1 2 3 4 5 6 25
Exemple (5)
Une fois le tableau annexe rempli, il faut le
recopier dans le tableau initial
• À faire à chaque étape
• Avec les bons indices
• Attention aux paramètres des appels récursifs
2013-2014 Algorithmique 26
Pourquoi ça marche ?
On peut prouver par récurrence sur n
qu’on peut trier tout tableau de taille
inférieure ou égale à 2n :
• Pour n=0, c’est évident
• Si c'est vrai pour n, est-ce vrai pour n+1 ?
• On peut trier les deux sous-tableaux (ils ont une
taille 2n)
• On les fusionne avec l’algorithme vu
précédemment, qui fonctionne de façon triviale
• Donc le tableau est trié
2013-2014 Algorithmique 27
Algorithme efficace ?
Si on note C(n) le nombre
d’opérations qu'il faut pour trier un
tableau de taille n, on a :
• C(n) = 2* C(n/2) + n
(n opérations pour la fusion)
Si on résout la récurrence, on obtient
que :
• C(n) = Θ(n log2n)
2013-2014 Algorithmique 28
Algorithme efficace ? (2)
Pour un tri, n log2n est la complexité
temporelle optimale
Pourtant, ce n’est pas le tri le plus
utilisé
• Pas la meilleure constante (k n log2n)
• Surtout : on a besoin d'un deuxième ta-
bleau aussi grand que le premier (pro-
blème de complexité spatiale)
2013-2014 Algorithmique 29
Le tri rapide ou Quicksort
Principe
Algorithme
Exemple
Un peu de culture générale
Sir Charles Antony Richard Hoare : 1962
Encore un tri dichotomique
L'algorithme le plus utilisé au monde
2013-2014 Algorithmique 31
Le principe du Quicksort
On va séparer le tableau en deux parties,
puis les trier
Contrairement au tri fusion, la séparation
ne sera pas arbitraire
On n'aura plus besoin de fusionner
2013-2014 Algorithmique 32
Principe de la séparation
On choisit une valeur du tableau, qui
servira de pivot
On réorganise le tableau de façon à ce
que :
• Toutes les valeurs inférieures au pivot soient
placées avant lui dans le tableau
• Et toutes les valeurs supérieures après
2013-2014 Algorithmique 33
Implementation
int partition(int [] tableau, int deb, int fin){
int compt=deb;
int pivot=tableau[deb];
int i;
for(i=deb+1;i<=fin;i++){
if(tableau[i]<pivot){
compt++;
echanger(tableau,compt,i);
}
}
echanger(tableau,compt,deb);
return compt;
}
2013-2014 Algorithmique 34
Quelques remarques
Ici on considère que le premier élément
est le pivot
• Si ce n'est pas lui, un premier échange
suffit
On avance dans le tableau en remettant
systématiquement les valeurs inférieures
au pivot dans les premières cases
Le dernier échange met le pivot à sa place
2013-2014 Algorithmique 35
Exemple
3 4 1 5 6 2
3 4 1 5 6 2
3 4 1 5 6 2
3 4 1 5 6 2
3 1 4 5 6 2
3 1 4 5 6 2
3 1 4 5 6 2
2013-2014 Algorithmique 36
Exemple (2)
3 1 4 5 6 2
3 1 2 5 6 4
2 1 3 5 6 4
2 1 3 5 6 4
2 1 3 5 6 4
2 1 3 5 6 4
2 1 3 5 6 4
2013-2014 Algorithmique 37
Exemple (3)
2 1 3 5 6 4
1 2 3 5 6 4
1 2 3 5 6 4
1 2 3 5 6 4
1 2 3 5 6 4
1 2 3 5 6 4
1 2 3 5 6 4
2013-2014 Algorithmique 38
Exemple (4)
1 2 3 5 6 4
1 2 3 5 4 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
2013-2014 Algorithmique 39
Autres méthodes
Deux itérateurs, partant l'un du début+1 l'autre
de la fin (le pivot étant encore au début)
• Tant qu'on est plus petit que le pivot en partant du
début, on avance
• Tant qu'on est plus grand en partant de la fin, on
recule
• Si les deux positions ne sont pas confondues, on
échange
• Puis on recommence jusqu'à ce que les positions
soient confondues
2013-2014 Algorithmique 40
Ensuite
Une fois le tableau partitionné :
• on trie les deux « moitiés » (encore de la récursivité)
• autour du pivot (exclus, il est déjà à sa place)
Une fois qu'elles sont triées, pas besoin de
fusionner
• Les éléments du sous-tableau de gauche sont
forcément inférieurs à ceux du sous-tableau de droite
Cas d'arrêt encore une fois évident :
• moins de 2 cases
2013-2014 Algorithmique 41
Pourquoi ça marche ?
On prend un pivot
Les plus petits devant, les plus
grands derrière
Et on trie les deux parties autour du
pivot
2013-2014 Algorithmique 42
Algorithme efficace ?
Fortement dépendant du choix du pivot
• Choix optimal = clé médiane
• Pire des choix : le plus petit ou le plus grand
• Laisse une case et un tableau de n-1
• On se retrouve grosso modo au tri par sélection
Mais un choix du pivot optimal passe par
un autre algorithme
• D'où perte de temps
2013-2014 Algorithmique 43
En pratique
On tape au hasard
Pire des cas : on prend toujours le plus
grand ou le plus petit
Dans ce cas, on est en Θ(n²)
2013-2014 Algorithmique 44
En moyenne
Θ(n log2n)
Avec une constante inférieure à celle du tri
fusion
Ne nécessite pas de tableau annexe
2013-2014 Algorithmique 45
Efficace quand ?
Pour les structures de grande taille
Pour les petits tableaux, on lui préfère un
tri simple, comme la sélection ou l'insertion
Optimisation : en dessous d’une certaine
taille limite, on ne fait plus l’appel récursif
mais un tri par insertion
2013-2014 Algorithmique 46
