Références

Comme beaucoup de cours d'algorithmes, celui-ci s'appuie sur :

Algorithmique
, par
Introduction à l'algorithmique

Thomas Cormen, Charles Leiserson, Ronald Rivest

Alexandre Duret-Lutz
et Cliord Stein.
[email protected]

27 septembre 2010 Une grosse partie de ces transparents est dérivée de ceux de
Sylvain Peyronnet (donnés à l'Épita en 2005).
D'autres sont inspirés des supports de cours de Erik D. Demaine
et Charles E. Leiserson au MIT : http://ocw.mit.edu/OcwWeb/
Electrical-Engineering-and-Computer-Science/
6-046JFall-2005/LectureNotes/
A. Duret-Lutz Algorithmique 1 / 96 A. Duret-Lutz Algorithmique 2 / 96

Plan du cours Première partie I

Introduction : algorithmes et complexité

Notion d'algorithme
Partie 1 : Notion d'algorithme, complexité
1

Partie 2 : Tris et rangs 2 Mesure de complexité

Partie 3 : Structures de données Comment mesurer ?
Partie 4 : Principaux paradigmes Exemple du tri par insertion
Analyse asymptotique et ordres de grandeur
Rappel sur les arbres
Tri fusion
Théorème général pour les équations de récurrence

A. Duret-Lutz Algorithmique 3 / 96 A. Duret-Lutz Algorithmique 4 / 96

Notion d'algorithme Une dénition d'algorithme informelle
Un ensemble d'opérations de calcul élémentaires qui sont organisées
de façon à produire un ensemble de valeurs en sortie (output) à partir
1 Notion d'algorithme d'un ensemble de valeurs fournies en entrée (input).
Un algorithme résout toujours un problème de calcul. L'énoncé du
2 Mesure de complexité problème spécie la relation entrée/sortie souhaitée.
Comment mesurer ? Opérations de calcul élémentaires :
Exemple du tri par insertion
Analyse asymptotique et ordres de grandeur opérations arithmétiques,
Rappel sur les arbres lecture/aectation de variables,
Tri fusion comparaisons...
Théorème général pour les équations de récurrence
Organisation : (aussi appellé structure de contrôle )
tests,
boucles...
A. Duret-Lutz Algorithmique 5 / 96 A. Duret-Lutz Algorithmique 6 / 96

Exemples Une dénition formelle ?

1 Multiplication
Entrée : deux entiers a et b Donner une dénition précise de la notion d'algorithme est assez
Sortie : leur produit ab dicile et complexe.
Algorithme : celui de l'école Il existe plusieurs dénitions mathématiques depuis les années 30.
Plus Grand Commun Diviseur (PGCD)
Objectifs : pouvoir raisonner facilement sur les algorithmes, les
composer, les prouver, calculer le coût de leur exécution (temps,
2

Entrée : deux entiers a et b espace)

Sortie : pgcd (a, b)
Algorithme : celui d'Euclide fonctions récursives
3Test de primalité Entrée : un entier a λ-calcul
Sortie : vrai ssi a est premier machines de Turing
Algorithme : boucle pour tester tous les diviseurs ? RAM (ici :  Random Access Machine )
On parle plutôt de problème de décision dans le dernier cas : on veut
décider (plutôt que calculer) si a est premier.
A. Duret-Lutz Algorithmique 7 / 96 A. Duret-Lutz Algorithmique 8 / 96
Calculabilité Restriction des problèmes envisagés

Fait :
Toutes ces dénitions sont équivalentes Dans ce cours, on étudie seulement des problèmes pour lesquels il
Thèse de Church : existe des algorithmes.
Tout ce qui est calculable intuitivement est aussi En fait, on s'intéressera aux problèmes pour lesquels il existe des
calculable par les objets formels précédemment cités algorithmes ecaces.
Mais :
Il existe des problèmes non calculables (indécidables) Un exemple typique de problème décidable pour lequel il n'y a pas
Exemple : problème de l'arrêt d'algorithme ecace : le jeu d'échec (le nombre de congurations est
Entrée : Un algorithme (programme) A et une entrée I environ 10 ).
50

Sortie : A termine-t-il pour I ?

A. Duret-Lutz Algorithmique 9 / 96 A. Duret-Lutz Algorithmique 10 / 96

Mesure de complexité Mesure de complexité

1 Notion d'algorithme On veut une mesure pour comparer des algorithmes qui résolvent le
même problème (ou non !). On voudrait que la complexité :
2 Mesure de complexité ne dépende pas de l'ordinateur
Comment mesurer ? ne dépende pas du langage de programmation
Exemple du tri par insertion
Analyse asymptotique et ordres de grandeur ne dépende pas du programmeur
Rappel sur les arbres soit indépendante des détails l'implémentation
Tri fusion etc.
Théorème général pour les équations de récurrence

A. Duret-Lutz Algorithmique 11 / 96 A. Duret-Lutz Algorithmique 12 / 96

Random Access Machines Tri par insertion
On choisit de travailler sur un modèle d'ordinateur idéalisé.
RAM : Problème : Trier un tableau d'entiers
processeur unique Entrée : un tableau A d'entiers
Sortie : le tableau A trié par ordre croissant
instructions exécutées séquentiellement
mémoire innie InsertionSort(A)
accès aléatoires à la mémoire en temps constant 1 for j ← 2 to length(A) do
2 key ← A[j ]

Pour mesurer l'ecacité d'un algorithme, on va mesurer le temps 3 i ← j − 1

qu'il utilise. Il sut de compter les instructions et de les pondérer par 4 while i > 0 and A[i ] > key do
leur coût. 5 A[i + 1] ← A[i ]

6 i ← i − 1

On peut aussi vouloir mesurer la mémoire utilisée. 7 A[i + 1] ← key

(Concentrons-nous sur le temps pour l'instant.)

A. Duret-Lutz Algorithmique 13 / 96 A. Duret-Lutz Algorithmique 14 / 96

Tri par insertion : coût en temps Tri par insertion : cas favorable et défavorable
InsertionSort(A) coût fois Cas favorable : le tableau est trié. j = 1.
t
1 for j ← 2 to length(A) do c n 1

2 key ← A[j ] c n − 1
2
T n ( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 (n − 1) + c7 (n − 1)
3 i ← j − 1 c n − 1
P 3
C'est une fonction linéraire du style an + b.
4 while i > 0 and A[i ] > key do c Pnj= tj
5 A[i + 1] ← A[i ]
4
n
(t − 1)
2
Cas défavorable : le tableau P
est trié par ordre décroissant. tj = j.
Pnj = j Rappelons que nj= j = n(n+ ) − 1 et
c 5 2 1

6 i ← i − 1 c
j = tj − 1)
6 ( Pn n(n− ) .
2 2

j = (j − 1) =
2

7 A[i + 1] ← key n − 1
1
c 7 2 2

 
T n( ) = c1 n + c2 (n − 1) + c3 (n − 1) ( + 1)
( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 −1
n n

X n X n X n T n
2
+ c4 tj + c5 (tj − 1) + c6 (tj − 1) + c7 (n − 1)
( − 1) ( − 1)
+ c7 ( n − 1 )
n n n n
j =2 j =2 j =2 + c5 + c6
2 2
Cas le plus favorable ? Cas le plus défavorable ? C'est une fonction quadratique du style an 2
+ bn + c .
A. Duret-Lutz Algorithmique 14 / 96 A. Duret-Lutz Algorithmique 15 / 96
Cas moyen ? Indépendance vis-à-vis de la machine
Le cas le plus favorable est la borne inférieure
Le cas le plus défavorable est la borne supérieure
Le cas général se situe entre les deux (en toute logique !)
On fait parfois des analyses de  cas moyen  : Dans nos formules de T (n), les coecients c , c , . . . , c dépendent
1 2 7

Tableau d'entrée = n nombres tirés au hasard (on suppose une de la machine utilisée.
loi uniforme). Pour une cléf choisie ligne 2 en moyenne la moitié On souhaite :
du tableaux lui est supérieur et l'autre moitié lui est inférieure.
Donc tj = t . ignorer les constantes qui dépendent des machines,
P 2
P
On a nj= t = n(n+ )− et nj= t − 1 = n(n− )+
1 2 3 2 étudier la croissance de T (n) lorsque n → ∞.
2 2 4 2 2 4

n (n + 1) − 2 On fait une analyse asymptotique du temps de calcul

T (n ) = c n + c (n − 1) + c (n − 1) + c
=⇒
1 2
4 3 4

n (n − 3) + 2 n (n − 3) + 2
+c +c + c (n − 1)
4 5
4 6 7

C'est encore une fonction quadratique du style an + bn + c . 2

A. Duret-Lutz Algorithmique 16 / 96 A. Duret-Lutz Algorithmique 17 / 96

Comparaison de fonctions Concrètement...

n log ln n
40
3
n e n
2
n 2
n n
2n Supposons 10 opérations par seconde.
6

n log 2
n n n log 2
n n
2
n
3
2n
30 10 2
6.6 µs 0.1 ms 0.6 ms 10 ms 1s 4 · 10 ans
6

n log 10
n
10 3
9.9 µs 1 ms 10 ms 1s 16.6 min
10 4
13.3 µs 10 ms 0.1 s 1.6 min 11.6 j
20 n
10 5
16.6 µs 0.1 s 1.6 s 2.7 h 347 ans
10 6
19.9 µs 1s 19.9 s 11.6 j 10 ans
6

10 /2
10 7
23.3 µs 10 s 3.9 min 3.17 ans
10 26.6 µs 1.6 min 44.3 min 317 ans
n
8
√
n 10 9
29.9 µs 16.6min 8.3 h 31709 ans
ln n
0 5 10 15 20
A. Duret-Lutz Algorithmique 18 / 96 A. Duret-Lutz Algorithmique 19 / 96
Équivalence asymptotique de fonctions Complexité asymptotique du tri par insertion
Cas favorable
Θ(g (n)) = {f (n) | ∃c1 ∈ R+? , ∃c2 ∈ R+? , ∃n0 ∈ N, T n ( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 (n − 1) + c7 (n − 1)
∀n ≥ n0 , 0 ≤ c1 g (n) ≤ f (n) ≤ c2 g (n)} = Θ(n)
Impose que f et g soient positives asymptotiquement. Cas défavorable  
Par convention on note  f (n) = Θ(g (n))  au lieu de ( + 1)
( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 −1
n n

2
T n
 f (n) ∈ Θ(g (n)) 
( − 1) ( − 1)
+ c7 (n − 1) = Θ(n2 )
n n n n
Si a > 0, on a a n + a n + a = Θ(n ).
2 2
2
1 0
2 + c5
2
+ c6
2
Par exemple on pose c = et c = a , et on montre
a

2 1
2
2
3 2
2 Cas moyen
( + 1) − 2
a a a 3a ( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4
n n

4
2 1 0 2 T n
≤a + + ≤
2 |n {z n } 22
2
( − 3) + 2 ( − 3) + 2
+ c7 (n − 1) = Θ(n2 )
n n n n
n→∞ + c5 + c6
→0 quand
4 4
A. Duret-Lutz Algorithmique 20 / 96 A. Duret-Lutz Algorithmique 21 / 96

Simplions nous les calculs Calculs simpliés

Pour mesurer la complexité en temps on choisit une opération

fondamentale pour le problème de calcul particulier, et on calcule le InsertionSort(A) coût fois
nombre d'opérations fondamentales exécutées par l'algorithme. 1 for j ← 2 to length(A) do c n 1

Le choix est bon si le nombre total d'opérations est proportionnel au 2 key ← A[j ] c n − 1 2

nombre d'opérations fondamentales. 3 i ← j − 1 c n − 1

P 3

4 while i > 0 and A[i ] > key do c Pnj= tj

Exemples :
4 2
n
5 A[i + 1] ← A[i ] c
Pnj = j
(t − 1)5 2

problème opération fondamentale 6 i ← i − 1 c

j = (tj − 1)
6 2
addition des entiers binaires opération binaire 7 A[i + 1] ← key c n − 1 7

multiplication de matrices multiplication scalaire

tri d'un ensemble d'éléments comparaison des éléments

A. Duret-Lutz Algorithmique 22 / 96 A. Duret-Lutz Algorithmique 23 / 96

Calculs simpliés Complexité asymptotique du tri par insertion
Cas favorable
T n ( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 (n − 1) + c7 (n − 1)
InsertionSort(A) fois = Θ(n)
1 for j ← 2 to length(A) do Cas défavorable
2 key ← A[j ]  
3 i ← j − 1
( + 1)
( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 −1
n n
Pn 2
T n
4 while i > 0 and A[i ] > key do j =2 t j
5 A[i + 1] ← A[i ] ( − 1) ( − 1)
+ c7 (n − 1) = Θ(n2 )
n n n n
+ c5 + c6
6 i ← i − 1 2 2
7 A[i + 1] ← key Cas moyen
( + 1) − 2
( ) = c1 n + c2 (n − 1) + c3 (n − 1) + c4
n n

4
T n

( − 3) + 2 ( − 3) + 2
+ c7 (n − 1) = Θ(n2 )
n n n n
+ c5 + c6
4 4
A. Duret-Lutz Algorithmique 23 / 96 A. Duret-Lutz Algorithmique 24 / 96

Complexité asymptotique du tri par insertion Bornes asymptotiques supérieures et inférieures

Cas favorable
( )= −1
T n n
O( ( )) = {f (n) | ∃c ∈ R+? , ∃n0 ∈ N,
g n
= Θ(n)
∀n ≥ n0 , 0 ≤ f (n) ≤ cg (n)}
Cas défavorable Ω(g (n)) = {f (n) | ∃c ∈ R+? , ∃n0 ∈ N,
( + 1) ∀n ≥ n0 , 0 ≤ cg (n) ≤ f (n)}
−1
n n
( )=
2
T n

= Θ(n2 )
Notons que
Cas moyen f (n) = Θ(g (n)) ⇐⇒ f (n) = O(g (n))
et f (n) = Ω(g (n)).
( + 1) − 2
n n Ou encore Θ(g (n)) = O(g (n)) ∩ Ω(g (n)).
( )=
4
T n

Comme on a Θ(n) ⊆ O(n ) et Θ(n ) ⊆ O(n ), on pourra dire que le

2 2 2

temps d'exécution du tri par insertion de n éléments est en O(n ).

2
= Θ(n ) 2

A. Duret-Lutz Algorithmique 24 / 96 A. Duret-Lutz Algorithmique 25 / 96

Propriétés Exercices
Trouver deux fonctions f et g telles que f (n) 6= O(g (n)) et
g (n ) 6= O(f (n )).

On dit que deux fonctions peuvent être incomparables au sens

Si nlim
( )
g n
= c > 0 alors g (n) = Θ(f (n)). de O.
→∞ f (n ) Montrer que Θ(f (n) + g (n)) = Θ(max(f (n), g (n))).
g (n ) Si f (n) = Θ(g (n)), a-t-on 2f (n) = Θ(2g (n) ) ?
Si nlim = 0 alors g (n) = O(f (n)) et f (n) 6= O(g (n)). Justiez votre réponse (preuve si oui, contre-exemple si non).
→∞ f (n )

g (n )
Dénissons l'ordre (partiel) suivant :
Si nlim = ∞ alors f (n) = O(f (n)) et g (n) 6= O(f (n)).
→∞ f (n ) Θ(f (n)) ≤ Θ(g (n)) si f = O(g (n))
f (n ) = O(g (n )) ssi g (n ) = Ω(f (n )). Θ(f (n)) < Θ(g (n)) si f = O(g (n)) et g 6∈ O(f (n))
Énumérer par ordre croissant les ensembles Θ(. . .) des fonctions
suivantes : √
n
n , 2 , n log n , ln n , n + 7n , log n ,
5 n n− , n , n + log n,
n, e , 2
1 2 2

log log n, n , (log n) , n!, n .

3 2 /
3 2

A. Duret-Lutz Algorithmique 26 / 96 A. Duret-Lutz Algorithmique 27 / 96

Analyse avec les notations asymptotiques Arbres enracinés : dénition graphique

Arbre
Considérons la complexité dans un cas quelconque. Un arbre est un graphe non-orienté acyclique et connexe.
Arbre enraciné
InsertionSort(A) Un arbre enraciné est un arbre avec un sommet distingué. Ce
1 for j ← 2 to length(A) do Θ(n)+ sommet distingué s'appelle la racine de l'arbre.
2 do key ← A[j ] Θ(n)+ Les sommets sont de façon équivalente appelés n÷uds.
3 i ← j − 1 Θ(n)+ Soit x un n÷ud dans un arbre enraciné T de racine r . Un n÷ud
4 while i > 0 and A[i ] > key do O(n )+ 2
quelconque y sur l'unique chemin entre x et r est un ancêtre de x ;
5 do A[i + 1] ← A[i ] O(n )+ 2
réciproquement, x est un descendant de y . En parle d'ancêtre
6 i ← i − 1 O(n )+ 2
propre et de descendant propre si x 6= y . Si (y , x ) est le dernier arc
7 A[i + 1] ← key Θ(n) du chemin entre r et x , alors y est le père de x et x est un ls de
y . Une feuille est un n÷ud sans ls. (La racine est l'unique n÷ud
O(
n
2
)
sans père.) Le degré d'un n÷ud est son nombre de ls. La
profondeur de x est la longueur du chemin entre r et x . La hauteur
de T est la profondeur maximale de ses n÷uds.
A. Duret-Lutz Algorithmique 28 / 96 A. Duret-Lutz Algorithmique 29 / 96
Arbres enracinés : dénition mathématique Arbres enracinés : dénition récursive
Ensemble avec relation de précédence
A = {a, b , c , d , e , f , g , h , i } et ≺ précédence sur A :
1

a ≺ b, a ≺ c , a ≺ d , b ≺ e , b ≺ f , c ≺ g , f ≺ h, f ≺ i .
1 1 1 1 1 1 1 1 Dénition récursive
D'où une représentation arborescente de A. Un arbre enraciné est un ensemble de un ou plusieurs n÷uds tel
On note 4 la clôture réexive et transitive. que
4 relation d'ordre (non total) sur A. l'un des n÷uds r est désigné comme la racine
Ensemble ordonné le reste des n÷uds est partionné en n ≥ 0 ensembles disjoints
Soit (A, 4) un ensemble ordonné. ≺ est l'ordre strict associé à A. T , T , . . ., Tn tels que chacun de ces ensembles est lui-même
1 2

Maj( a) = {x ∈ A | a 4 x } Min( a) = {x ∈ A | x 4 a} un arbre. Les arbres T , T , . . ., Tn sont appelés sous-arbres

1 2

Maj?( a) = {x ∈ A | a ≺ x } Min?( a) = {x ∈ A | x ≺ a}
de r
Arbres  mathématiques  Le degré d'un n÷ud est le nombre de sous-arbres dont il est la
Un ensemble ordonné (A, 4) est un arbre ssi racine.
A est ni

A possède un unique plus petit élément appelé racine

∀a ∈ A, Min(a) est totalement ordonné.

A. Duret-Lutz Algorithmique 30 / 96 A. Duret-Lutz Algorithmique 31 / 96

Arbres ordonnés, arbres binaires Propriétés d'arbre (1/2)

Arbres ordonnés
Un arbre ordonné est un arbre enraciné dans lequel les ls d'un Tout arbre présentant n sommets possède n − 1 arrêtes.
n÷ud sont ordonnés. Preuve par récurrence. Facile de se convaincre en considérant
On peut parler de premier sous-arbre, troisième ls, etc. que seule la racine d'un arbre n'a pas de père.
Arbre binaire Un arbre binaire non vide de f feuilles possède f − 1 n÷uds de
Un arbre binaire est un ensemble ni de n÷uds qui est soit vide, degré 2.
soit formé d'un n÷ud racine et de deux arbres disjoints appelés Preuve par récurrence sur le nombre de feuille f > 0 de l'arbre A.
sous-arbre gauche et sous-arbre droit. Trois cas se présentent pour le cas de récurence :
Une feuille est un n÷ud dont les sous-arbres associés sont vides. Soit A est le regroupement de Ag et Ad avec fg + fd = f . On a
alors n = 1 + ng + nd = 1 + (fg − 1) + (fd − 1) = f − 1.
Un arbre binaire n'est pas un arbre ordonné dont les n÷uds seraient Soit A est le regroupement de Ag et ε, alors forcément
de degré au plus 2. Un arbre binaire peut avoir un sous-arbre gauche n = ng = fg − 1 = f − 1.
vide (i.e., seulement un ls droit). Soit A est le regroupement de ε et Ad , idem.
L'arbre binaire vide, noté ε, n'est pas un arbre. Tous les autres arbres
binaires en sont.
A. Duret-Lutz Algorithmique 32 / 96 A. Duret-Lutz Algorithmique 33 / 96
Propriétés d'arbre (2/2) Arbres équilibrés
Arbre binaire complet
Un arbre binaire non vide est complet si tous ses n÷uds sont de
Le nombre de feuilles d'un arbre binaire de hauteur h est d'au degré 2 ou 0.
plus 2h . (Preuve par récurrence sur h.) Les nombres de n÷uds et de feuilles d'un arbre binaire complet
Un arbre binaire de f > 0 feuilles possède une hauteur d'au sont liés par n = 2f − 1. (Preuve : on a vu qu'un arbre binaire non
moins dlog f e. (Conséquence directe.) vide possède f − 1 n÷uds de degré 2.)
Le nombre de n÷ud d'un arbre binaire de hauteur h est d'au Arbre binaire équilibré
plus 2h+ − 1. (Preuve par récurrence sur h.)
1 Un arbre binaire non vide A est équilibré si les longueurs de deux de
Un arbre binaire de n > 0 n÷uds possède une hauteur d'au ses branches ne peuvent diérer que d'1 au plus.
moins dlog(n + 1) − 1e = blog nc. (Conséquence directe.) Les feuilles d'un tel arbre se situent soit à la profondeur
p = blog(n + 1) − 1c soit à la profondeur p = dlog(n + 1) − 1e.
0

(Un tel arbre n'est pas forcément complet.)

On retient h = blog nc pour les arbres binaires équilibrés.
A. Duret-Lutz Algorithmique 34 / 96 A. Duret-Lutz Algorithmique 35 / 96

Tri fusion Arbre de récursion

Problème : Trier un tableau d'entier
Entrée : un tableau A d'entier, premier indice l , dernier indice r Résolvons T (n) = 2T (n/2) + cn pour une constante c > 0.
Sortie : le tableau A trié par ordre croissant cn cn

Merge-Sort(A, l , r ) T(1) ( )
T n
cn /2 cn /2 cn
1 if l < r then Θ(1) Θ(1)

= blog nc
2 q ← b(l + r )/2c Θ(1)
3 Merge-Sort(A, l , q ) T (bn /2c) cn /4 cn /4 cn /4 cn /4 cn
3 Merge-Sort(A, q + 1, r ) T (dn /2e)
h

4 Merge(A, l , q , r ) Θ(n)
Θ(1) Θ(n)
On a donc la relation de récurrence
( n feuilles
Θ(1) si n = 1
T (n ) = On a donc T (n) = Θ(n log n).
2T (n/2) + Θ(n) si n > 1
A. Duret-Lutz Algorithmique 36 / 96 A. Duret-Lutz Algorithmique 37 / 96
Théorème général Applications du théorème
Soit à résoudre
( ( ) = 2T (n/2) + Θ(n)
T n
Θ(1) si n ≤ n 0 a = b = 2, n
logb a
= n. On a donc T (n) = Θ(n log n).
T (n ) =
aT (n /b ) + f (n ) si n > n √
T (n ) = 4T (n /2) +
0
n
√
avec a ≥ 1, b > 1, n ∈ N. 0 a = 4, b = 2, n
logb a
= n2 .  = 1 et n = O(n2−1 ), on a donc
Alors 2
T (n ) = Θ(n )

Si f (n) = O(n b a−ε ) pour un ε > 0, alors T (n) = Θ(n b a ).

log log

( ) = 3T (n/3) + n2
Si f (n) = Θ(n b a ), alors T (n) = Θ(n b a log n).
T n
log log
logb a
a = 3, b = 3, n = n.  = 1 et n = Ω(n + ), d'autre part
2 1 1

Si f (n) = Ω(n b a+ε ) pour un ε > 0, et si af (n/b) ≤ cf (n)

log
3(n/3) ≤ cn pour c = 1/3, a
2 2
donc T (n) = Θ(n ). 2

pour une constante c < 1 et tous les n susament grands, alors

T (n ) = Θ(f (n )). ( ) = 4T (n/2) + n2 / log n
T n
logb a
a = 4, b = 2, n = n2 . Mais on ne peut pas trouver d'ε > 0
Attention, il y a des trous dans ce théorème : un fonction f (n) peut tel que n2 / log n = O(n2−ε ). En eet n2 / log n ≤ cn2−ε implique
n'être prise en compte par aucun des trois cas. Le ε force la fonction n ≤ c log n . Le théorème ne s'applique pas.
ε

f (n ) a être polynomialement plus grande ou plus petite que n b a. log

A. Duret-Lutz Algorithmique 38 / 96 A. Duret-Lutz Algorithmique 39 / 96

Deuxième partie II Tris comparatifs

Tris et rangs
3 Tris comparatifs 4 Tris linéaires
Tris comparatifs 4 Tris linéaires Dénition Tri par dénombrement
Tri par paquets
3

Dénition Tri par dénombrement Rappel des tris par insertion

Rappel des tris par insertion Tri par paquets et fusion 5 Mélange aléatoire
et fusion Tri par sélection
5 Mélange aléatoire Tri par tas Recherche dans un tableau trié
Tri par sélection 6

Tri par tas 6 Recherche dans un tableau trié Structure de tas

Opérations sur le tas 7 Rangs et médians

Tri rapide Minimum
Structure de tas

Opérations sur le tas 7 Rangs et médians

Tri rapide Minimum Tri introspectif Sélection
Tri introspectif Sélection Bornes de complexité des Sélection stochastique
Bornes de complexité des Sélection stochastique tris comparatifs Sélection en O(n)
tris comparatifs Sélection en O(n)
A. Duret-Lutz Algorithmique 40 / 96 A. Duret-Lutz Algorithmique 41 / 96
Le problème Complexité d'un problème
Dénition
La complexité C (n) d'un problème P est la complexité du meilleur
Entrée : Une séquence de n nombres ha , a , . . . an i
1 2
algorithme qui résout P .
Sortie : Une permutation ha0 , a0 , . . . an0 i de la séquence d'entrée telle
1 2
Conséquences
que a0 ≤ a0 ≤ · · · ≤ an0 .
1 2
Si un algorithme A résout P en O(f (n)), alors
C (n ) = O(f (n )).
Souvent les entiers sont une partie d'une donnée plus complexe, Si l'on prouve que tous les algorithmes qui résolvent P ont
l'entier est alors la clé de la donnée. Et on triera les données d'après une complexité en Ω(g (n)), alors C (n) = Ω(g (n)).
les clés. Si ces bornes sont de grandeur équivalentes (i.e.,
La structure représentant A est généralement un tableau. f (n ) = Θ(g (n ))) alors C (n ) = Θ(f (n )) = Θ(g (n )), c'est la
Pour l'instant on ne s'intéresse qu'aux tris comparatifs : l'ordre des complexité du problème.
valeurs ne peut être déterminé qu'en les comparant entre elles. Pour l'instant, on a prouvé que la complexité du tri de n éléments est
dans O(n ).2

cela ne veut pas dire qu'il est impossible de faire mieux

il est toujours possible de faire pire
A. Duret-Lutz Algorithmique 42 / 96 A. Duret-Lutz Algorithmique 43 / 96

Résumé des épisodes précédents Tri par sélection

Tri par insertion On cherche le minimum du tableau A[1..n] et on l'échange avec la
En O(n ). 2 première position. On cherche le minimum du tableau A[2..n] et on
On en déduit que la complexité du problème du tri comparatif est l'échange avec la deuxième position, etc. Après k
en O(n ).2 recherches/échanges, A[1..k ] est trié.
Tri fusion Select-Sort(A) ( )
T n
En Θ(n log n). 1 for i from 1 to n do Θ(n)
On en déduit que la complexité du problème du tri comparatif est 2 min ← i Θ(n)
en O(n log n). 3 for j from i to n do Θ(n2 )
4 if A[j ] < A[min] then min ← j Θ(n2 )
Ce n'est pas incompatible puisque O(n log n) ⊂ O(n ). 2
5 A[min ] ↔ A[i ] Θ(n)
Le tri par insertion se fait en place (nombre de variables auxiliaires Θ(n2 )
indépendant de n). Le tri fusion demande un tableau temporaire pour
la fusion, il n'est pas en place. C'est pire que InsertionSort qui est dans O(n ) mais pas dans Ω(n ).
2 2

Ces deux tris sont stables : l'ordre des éléments égaux est préservé. Tri en place, mais instable (à cause de l'échange).
A. Duret-Lutz Algorithmique 44 / 96 A. Duret-Lutz Algorithmique 45 / 96
Arbre parfait Arbre parfait partiellement ordonné et tas
Un arbre parfait partiellement ordonné est un arbre parfait étiqueté de
façon à ce que l'étiquette d'un n÷ud soit supérieure à celles de ses
Un arbre parfait est un arbre binaire équilibré dont les feuilles du ls.
dernier niveau sont toutes à gauche.
18
12 11
6 10 9 4
2 3 8

Un tas est un tableau qui peut s'interpréter comme un arbre parfait

partiellement ordonné.
18 12 11 6 10 9 4 2 3 8
A. Duret-Lutz Algorithmique 46 / 96 A. Duret-Lutz Algorithmique 47 / 96

Propriétés d'un tas Opérations sur le tas (1) : Heapify

18 Entrée : un tableau A et deux indices i et m tels que A[LeftChild(i )] et
12 11 A[RightChild(i )] soient des racines de tas dans A[1..m],
Sortie : le tableau A tel que A[i ] soit une racine de tas.

6 10 9 4 Heapify(A, i , m)
2 3 8 1 l ←LeftChild(i ) ( ) ≤ T (2n/3) + Θ(1) avec n la
T n
2 r ←RightChild(i ) taille du sous-arbre commençant en i
A = 18 12 11 6 10 9 4 2 3 8 3 if l ≤ m and A[l ] > A[i ] et 2n/3 le nombre maximum de
4 then largest ← l n÷uds du sous-arbre recursivement
L'indice 1 correspond à la racine 5 else largest ← i exploré.
Parent(i ) = bi /2c (si i > 0) 6 if r ≤ m and A[r ] > A[largest ]
7 then largest ← r On en déduit T (n) = O(log n)
LeftChild(i ) = 2i (s'il existe)
8 if largest 6= i then Aussi T (h) = O(h) avec h la hauteur
RightChild(i ) = 2i + 1 (s'il existe) 9 A[i ] ↔ A[largest ] de l'arbre commençant à i .
10 Heapify(A, largest , m)
La propriété du tas : ∀i > 0, A[Father(i )] ≥ A[i ].
A. Duret-Lutz Algorithmique 48 / 96 A. Duret-Lutz Algorithmique 49 / 96
Opérations sur le tas (2) : Build-Heap Opérations sur le tas (3) : Build-Heap
Calculons T (n) pour Build-Heap de façon plus précise.
Entrée : un tableau A quelconque. La hauteur d'un tas de n n÷uds est blog nc.
Sortie : le tableau A réordonné en tas. Le nombre de sous arbres de hauteur h dans un tas de n n÷uds est
Build-Heap(A)
1 for i ← blength(A)/2c down to 1 do au plus dn/2h+ e. 1

2 Heapify(A, i , length(A)) La complexité d'Heapify sur une hauteur h est O(h).

Les éléments entre length(A)/2 + 1 et la n du tableau sont les On en déduit :
feuilles de l'arbre est sont déjà des tas. On corrige le reste du tableau blog nc l m

blog nc
 
blog nc

X X X
en remontant. ( )=
n
O( ) = O n
h
 = O n h

2h+1 2h+1 2h
T n h

Naïvement si n = length(A), T (n) = Θ( n ) O(log n ) = O(n log n ). h=0 h=0 h =0

| {z } | {z }
la boucle Heapify

Mais en réalité le temps passé dans Heapify dépend de la taille du

∞
X
k
∞
X 1/2
Comme on a = 2.
x h
kx = =
sous-arbre. (1 − x ) 2
2 (1 − 1/2)2
h
k =0 h=0
On obtient T (n ) = O(n ).

A. Duret-Lutz Algorithmique 50 / 96 A. Duret-Lutz Algorithmique 51 / 96

Algorithme du tri par tas Tri rapide

Origine
Sir Charles Antony Richard Hoare, 1962.
Heap-Sort(A) Tri en place et instable.
1

1 Build-Heap(A)
2 for i ← length(A) down to 2 do Idée générale
3 A[1] ↔ A[i ] On partage le tableau en deux sous-tableaux tels que tous les
4 Heapify(A, 1, i − 1) éléments du premier soient plus petits que ceux du second. On trie
ces deux tableaux recursivement.
On a bien sûr :
Comment partager ?
T n( )= O ( )
n
| {z }
+O( |{z}
n log
|{z}
n ) = O(n log n ) On choisit une clé, qui sert de pivot. Par échanges successifs, on
Build-Heap
boucle Heapify ordonne le tableau en deux blocs :
au début, les éléments inférieurs (ou égaux) au pivot
à la n, les éléments supérieurs (ou égaux) au pivot
Notre choix : le pivot est le premier élément.
O( n )
1. prétendument, car la récursion consomme de l'espace en log
A. Duret-Lutz Algorithmique 52 / 96 A. Duret-Lutz Algorithmique 53 / 96
Tri rapide : algorithme Complexité du tri rapide
Cas défavorable
Entrée : un tableau A d'entier, Entrée : un tableau A d'entier, Le partionnement crée un arbre de découpe très déséquilibré.
premier indice l , dernier indice r premier indice l , dernier indice r Cela se produit si l'entrée est déjà triée (dans un sens ou l'autre).
Sortie : le tableau A trié par Sortie : un entier p et le tableau A
ordre croissant réordonné tq A[l ..p] ≤ A[p + 1..r ]. T n ( ) = Θ(n) + Θ(1) + T (n − 1)
Quick-Sort(A, l , r ) Partition(A, l , r ) = T (n − 1) + Θ(n)
1 if l < r then 1 x ← A[l ] ; i ← l − 1 ; j ← r + 1 = Θ(n2 )
2 p ← Partition(A, l , r ) 2 repeat forever
3 Quick-Sort(A, l , p) 3 do i ← i + 1 until A[i ] ≥ x Cas favorable
4 Quick-Sort(A, p + 1, r ) 4 do j ← j − 1 until A[j ] ≤ x Le partionnement crée un arbre de découpe équilibré.
5 if i < j then
6 A[i ] ↔ A[j ] ( ) = Θ(n) + 2T (n/2)
T n

7 else
8 return j C'est la même équation que pour le tri fusion. On sait que la
T (n) = Θ(n) si n = r − l + 1.
Partition
solution est T (n) = Θ(n log n).
A. Duret-Lutz Algorithmique 54 / 96 A. Duret-Lutz Algorithmique 55 / 96

Intuition de la complexité moyenne (1) Intuition de la complexité moyenne (2)

Dans le cas général, on peut imaginer que les partitions vont être
Supposons un arbre déséquilibré  1/10 : 9/10  aléatoirement entre  bonnes  et  mauvaises .
  Exemple extrême
 n
 9n On suppose qu'on alterne une fois sur deux une M auvaise partition
T (n ) = T +T + Θ(n)
10 10 (1 : n − 1) et une B onne partition (dn/2e : bn/2c).
On dessine l'arbre de récursion. La branche la plus courte mesure M (n ) = B (n − 1) + Θ(n )
log n = Θ(log n) : la complexité de l'abre limité à ce niveau est
10
B (n ) = 2M (n /2) + Θ(n )
Θ(n log n). On en déduit que T (n) = Ω(n log n). La plus longue
branche à une hauteur de log / n et le coût à chaque niveau est
10 9

≤ n. En en déduit que T (n) ≤ n log / n = O(n log n). Finalement

10 9 On en déduit
T (n ) = Θ(n log n ). ( ) = 2M ((n − 1)/2) + Θ(n/2) + Θ(n)
M n

= 2M ((n − 1)/2) + Θ(n)

Toute partition selon un facteur constant implique
T (n ) = Θ(n log n ). = Θ(n log n)

A. Duret-Lutz Algorithmique 56 / 96 A. Duret-Lutz Algorithmique 57 / 96

Calcul de la complexité moyenne (1) Calcul de la complexité moyenne (2)
On suppose une distribution uniforme des partitions.
La partition coupe A[1..n] en A[1..i ] et A[i + 1..n] avec n − 1 choix n− !
possibles pour i . 2(n − 2) X 2

T (n ) = T (n − 1) + T (i ) + c (n − 1 + 1)
(n − 1)(n − 2) i= 1
n −1 n −1  
1X 2 X 2 n − 2 n − 2
T (n ) = (T (i ) + T (n − i )) + Θ(n) = ( ) + cn = T (n − 1) + T (n − 1) + c (n − 1) 1− +c
n − 1 − 1 i =1
T i
n n − 1 n − 1 n − 1
i =1
D'autre part : T (n − 1) + 2c
n
=
n − 1
n−2
2 X
( − 1) = ( ) + c (n − 1) On divise à droite et à gauche par n :
− 2 i =1
T n T i
n

Cherchons à faire apparaître T (n − 1)

dans T (n) : ( )
T n T n( − 1) 2c
! = +
n− n − 1
2(n − 2) X 2 n n
T (n ) = T (n − 1) + T (i ) + c (n − 1 + 1)
(n − 1)(n − 2) i= 1

A. Duret-Lutz Algorithmique 58 / 96 A. Duret-Lutz Algorithmique 59 / 96

Calcul de la complexité moyenne (3) Questions

T n ( ) ( − 1)
T n 2c
= +
n n − 1 n

on pose Y (n) = T n(n) Que se passe-t-il si tous les éléments du tableau à trier ont la
n
même valeur ?
2c X 1
(n) = Y (n − 1) + = 2c
On a l'impression qu'un tableau aléatoire sera trié plus
Y
n i
i =1
n rapidement qu'un tableau trié. Comment faire en sorte que
X 1 l'algorithme aie la même complexité (en moyenne) sur les
T n ( ) = 2cn
i =1
i
tableaux aléatoires que sur les tableaux triés ?
Pn 1
La formule d'Euler : i =1 i = ln n + γ + o (1).
On en déduit
T n ( ) = Θ(n)Θ(log n) = Θ(n log n)
A. Duret-Lutz Algorithmique 60 / 96 A. Duret-Lutz Algorithmique 61 / 96
Tri rapide stochastique Autre idée : pivot médian
L'idée est simple : on choisit le pivot aléatoirement dans le tableau.
RandomizedPartition(A, l , r )
1 x ← A[Random(l , r )] ; i ← l − 1 ; j ← r + 1
2 repeat forever (La médiane de 2k + 1 valeurs est la (k + 1) plus grande valeur.)
e

4 do j ← j − 1 until A[j ] ≤ x
3 do i ← i + 1 until A[i ] ≥ x L'idée : on choisit comme pivot pour la partition la médiane de
5 if i < j then quelques valeurs du tableau.
6 A[i ] ↔ A[j ]
Par exemple la médiane des trois premières valeur.
7 else Ou mieux (pourquoi ?) : la médiane des A[l ], A[b l +r c] et A[r ].
8 return j 2

L'eet est le même que si l'on avait mélangé le tableau avant de la

trier. Au lieu de supposer la distribution d'entrée, on l'a imposée.
Avantage : aucune entrée particulière ne provoque le pire cas ; celui-ci
ne dépend que du générateur aléatoire.
A. Duret-Lutz Algorithmique 62 / 96 A. Duret-Lutz Algorithmique 63 / 96

Conclusion sur le tri rapide Tri introspectif

Origine
On a T (n) = O(n ) de façon générale, mais T (n) = Θ(n log n)
2
David Musser, 1997
en moyenne sur des entrées distribuées uniformément. Utilisé dans la Standard Template Library de SGI. (std::sort)
En pratique le tri rapide est plus rapide que les autre tris Intérêt
présentés jusqu'à présent pour des valeurs de n pas ridiculement Modication du tri rapide de façon à ce que T (n) = Θ(n log n)
petites. toujours. Donc : tri en place et instable.
2

Pour les petites valeurs, le tri par insertion est un bon choix. Idée
Détecter les séquences qui posent problème au tri rapide, et
L'implémentation de qsort() dans la GNU Libc (et d'autres) : eectuer un tri par tas dans ce cas.
Version non-récursive du tri rapide. En pratique
Choix du pivot médian des extrémités et du milieu.

≤4
On borne le nombre d'appels récursifs à O(log n).
Tri par insertion dès que la partition possède éléments.
Musser suggère 2blog nc.
2. prétendument, comme pour le QuickSort
A. Duret-Lutz Algorithmique 64 / 96 A. Duret-Lutz Algorithmique 65 / 96
Tri introspectif : algorithme Résumé des complexités

IntroSort(A, l , r ) complexité en moyenne

1 IntroSort'(A, l , r , 2blog(r − l + 1)c) Tri par insertion O(n ) 2
Θ(n ) 2

IntroSort'(A, l , r , depth_limit ) Tri fusion Θ(n log n)

1 if depth_limit = 0 then Tri par sélection Θ(n ) 2

2 Heap-Sort(A, l , r ) Tri par tas O(n log n)

3 return Tri rapide O(n ) 2
Θ(n log n)
4 else Tri introspectif O(n log n)
5 depth _limit ← depth _limit − 1
On sait donc que le problème du tri comparatif est en O(n log n).
6 p ← Partition(A, l , r )
On va maintenant montrer que ce problème est en Ω(n log n),
7 IntroSort'(A, l , p, depth_limit ) c'est-à-dire qu'un tri comparatif ne peut pas être moins complexe
8 IntroSort'(A, p + 1, r , depth_limit ) dans le cas général.

A. Duret-Lutz Algorithmique 66 / 96 A. Duret-Lutz Algorithmique 67 / 96

Borne inférieure sur le tri comparatif Tris linéaires

Rappel du problème
Entrée : Une séquence de n nombres ha , a , . . . an i
1 2

Sortie : Une permutation ha0 , a0 , . . . an0 i de la séquence d'entrée 3 Tris comparatifs 4 Tris linéaires
1

telle que a0 ≤ a0 ≤ · · · ≤ an0 .

2
Dénition Tri par dénombrement
Argumentation
1 2
Rappel des tris par insertion Tri par paquets
Les tris peuvent être représentés par un arbre binaire (dit  de et fusion 5 Mélange aléatoire
décision ). Les n÷uds internes sont des comparaisons entre deux Tri par sélection
éléments : le ls gauche désigne une réponse négative et le ls Tri par tas 6 Recherche dans un tableau trié
droit une réponse positive. Les feuilles représentent la permutation Structure de tas

Rangs et médians
à eectuer pour obtenir le tableau trié.
Opérations sur le tas 7

Tri rapide Minimum

Il existe n! permutations possibles de ha , a , . . . an i. Notre arbre
1 2 Tri introspectif Sélection
binaire possède n! feuilles, sa hauteur est donc au moins dlog n!e. Bornes de complexité des Sélection stochastique
On en déduit T (n) = Ω(log(n!)) = Ω(n log n).    tris comparatifs Sélection en O(n)
√  n n 1
Rappel de la formule de Stirling : n! = 2πn 1+Θ .
e n

A. Duret-Lutz Algorithmique 68 / 96 A. Duret-Lutz Algorithmique 69 / 96

Tri par dénombrement Tri par paquets
Caractéristique
Tri stable, mais pas en place. Caractéristique
Utilisable uniquement si les éléments en entrée sont dans un petit Tri ni stable, ni en place. Suppose les éléments de l'entrée répartis
intervalle. Ici on les suppose dans [[1, k ]]. uniformément. Ici on considère l'intervalle [0, 1[.
Algorithme Algorithme
CountingSort(A, B , k ) BucketSort(A)
1 for i ← 1 to k do C [i ] ← 0 Θ(k ) 1 n ← length(A) Θ(n)
2 for i ← 1 to length(A) do C [A[j ]] ← C [A[j ]] + 1 Θ(n) 2 for i ← 1 to n do Θ(n)
3 for i ← 1 to k do C [i ] ← C [i ] + C [i − 1] Θ(k ) 3 insert A[i ] into the list B [bn · A[i ]c] Θ(n)
4 for i ← length(A) down to 1 do Θ(n) 4 for i ← 0 to n − 1 do Pn −
Θ(n)
5 5 sort B [i ] with InsertionSort i = O(ni )
1 2
B [C [A[i ]]] ← A[i ] Θ(n) 0

6 C [A[i ]] ← C [A[i ]] − 1 Θ(n) 6 concatenate B [0], B [1], . . ., B [n − 1] together in order Θ(n)

Θ(n) + Θ(k ) Complexité
Complexité Tout dépend de la taille ni des B [i ] à trier.
Si k = O(n), alors T (n) = Θ(n).
A. Duret-Lutz Algorithmique 70 / 96 A. Duret-Lutz Algorithmique 71 / 96

Complexité du tri par paquets Rappels probabilistes

Cas favorable
Si les B [i ] sont de taille ni = 1, les n appels à InsertionSort de la Espérance d'une variable aléatoire
ligne 5 prennent tous Θ(1). C'est sa X
valeur attendue, ou moyenne.
On obtient une complexité en Θ(n). E[ X ]= x Pr{ X = x}
x
Cas défavorable
Si (1) tous les éléments se retrouvent dans le même paquet, et (2) Variance
se paquet est ordonné à l'envers (pire cas pour le tri par insertion), Var[ X ] = E[(X − E[X ])2 ] = E[X 2 ] − E2 [X ]
alors la ligne 5 demande Θ(n ) opérations.
2
Loi binomiale
On obtient une complexité en Θ(n ). 2
On lance n ballons dans r paniers. Les chutes dans les paniers sont
Cas moyen équiprobables (p = 1/r ). On note Xi le nombre de ballons dans le
Que vaut ni en moyenne ? panier i . On a Pr{Xi = k } = Ckn pk (1 − p)n−k . On peut montrer
Que vaut nPi en moyenne ?
2
E [Xi ] = np et Var[Xi ] = np (1 − p ).
Que vaut ni =− O(E [ni ]) ?
1
0
2

A. Duret-Lutz Algorithmique 72 / 96 A. Duret-Lutz Algorithmique 73 / 96

Tri par paquet : étude probabiliste Mélange aléatoire
Notons ni la taille d'un paquet à trier avec un tri par insertion.
Si les valeurs à triées sont uniformément réparties leur répartitions Tris linéaires
dans les diérents paquets sont équiprobable. On se retrouve dans la 3 Tris comparatifs 4

Dénition Tri par dénombrement

situation d'envoyer n ballons dans n paniers (p = 1/n). Tri par paquets
1 Rappel des tris par insertion
On a donc E [ni ] = np = 1 et Var[ni ] = np(1 − p) = 1 − . et fusion 5 Mélange aléatoire
n
Tri par sélection
Le tri par insertion de n éléments prend O(n ). Pour tous les B [i ] on a
2
Tri par tas 6 Recherche dans un tableau trié
Structure de tas
! !
n −1
X n −1
X n −1
X
Opérations sur le tas 7 Rangs et médians
O( [ i ]) = O
E n
2
E[ni ] = O
2
E2[ni ] + Var[ni ] Tri rapide Minimum
i =0 i =0 i =0 Tri introspectif Sélection
nX −1  !
1 Bornes de complexité des Sélection stochastique
=O 1+1− = O(n) tris comparatifs Sélection en O(n)
n
i =0
Finalement T (n ) = O(n ) + Θ(n ) = Θ(n ) en moyenne.
A. Duret-Lutz Algorithmique 74 / 96 A. Duret-Lutz Algorithmique 75 / 96

Mélange naïf Mélange naïf : étude (1/2)

Si i valeurs ont été prises, la probabilité de choisir un j tel que
Entrée : un tableau A C [j ] = 0 est
i
. La probabilité de tomber sur un mauvais  j  k fois
Sortie : une copie B mélangée n

NaiveRandomizeArray(A) de suite avant d'en trouver

 k  un bon est
1 for i ← 1 to length(A) do C [i ] ← 0 Pr{ti + − 1 = k } = n
1
i
1− .
i

2 for i ← 1 to length(A) do On en déduit

n

3 do ∞
X ∞  k
4 j ←Random(1, length (A))
−i X
E[ i +
t − 1] = k Pr{ i +
t − 1 = k} =
n i
k
5 until C [j ] = 0
1 1
n n
k =0 k =0
6 C [j ] ← 1
Pour |x | < 1 on sait
P∞ k
x =
1
. En dérivant et en multipliant
7 B [i ] ← A[j ] P∞ k =0k x
1−x

8 return B par x on obtient k =0 kx = (1−x )2 .

Notons ti le nombre d'exécutions de la ligne 4 au sein d'une itération Il en découle que
de la boucle principale pour un i donné, et n la taille de A. −i i −i i
E[ i +
t 1 − 1] =
n
n

=
n
n
(n−i )
=
i

1 − ni 2
2
n n n −i
n2
A. Duret-Lutz Algorithmique 76 / 96 A. Duret-Lutz Algorithmique 77 / 96
Mélange naïf : étude (2/2) Mélange plus mieux
−1
E[ i ] = 1 +
t
i

n − i + 1
=
n
n

+1−i
Le nombre moyen d'exécutions de la ligne 4 est Entrée : un tableau A
n n n Sortie : le tableau A mélangé
X X X 1 BetterRandomizeArray(A)
E[ i ] =
t
n

n + 1 − i
= n

i =1 i =1
k =n+1−i
k =1
k 1 for i ← 1 to length(A) − 1 do
= n(ln n + Θ(1)) = Θ(n log n) 2 j ←Random(i , length (A))

3 A[i ] ↔ A[j ]
On en déduit que la complexité moyenne de ce mélange est
T (n ) = Θ(n log n ). On a évidement T (n) = Θ(n) dans tous les cas.
Dans le meilleur cas, on a T (n) = Θ(n) (le random est toujours le
bon !).
Dans le pire cas (le random est toujours le mauvais) l'algorithme ne
termine pas. Oups !
A. Duret-Lutz Algorithmique 78 / 96 A. Duret-Lutz Algorithmique 79 / 96

Recherche dans un tableau trié Recherche dans un tableau trié

Entrée : un tableau A[l ..r ], une valeur v
3 Tris comparatifs 4 Tris linéaires Sortie : un indice i ∈ [[l , r ]] tel que A[i ] = v ou 0 si v 6∈ A[l ..r ].
Dénition Tri par dénombrement BinarySearch(A, l , r , v )
Rappel des tris par insertion Tri par paquets 1 if l ≤ r then
et fusion Mélange aléatoire 2 m ← b(l + r )/2c

3 if v = A[m] then
5
Tri par sélection
Tri par tas 6 Recherche dans un tableau trié 4 return m
Structure de tas 5 else
Opérations sur le tas 7 Rangs et médians 6 if v < A[m] then
Tri rapide Minimum 7 return BinarySearch(A, l , m − 1, v )
Tri introspectif Sélection 8 else
Bornes de complexité des Sélection stochastique 9 return BinarySearch(A, m + 1, r , v )
tris comparatifs Sélection en O(n) 10 else
11 return 0
A. Duret-Lutz Algorithmique 80 / 96 A. Duret-Lutz Algorithmique 81 / 96
Recherche dans un tableau trié (compexité) Arbre de décision pour une recherche par
comparaison (1/2)
( ) ≤ T (n/2) + Θ(1)
T n L'arbre de décision pour un algorithme de recherche dans un tableau
A est un arbre binaire dont les n÷uds internes sont étiquetés par des
On en déduit T (n) = O(log(n)). indices de A de la façon suivante :
On peut montrer que cette complexité est optimale. la racine est étiquetée par l'indice du premier élément avec
Concentrons nous sur le cas v 6∈ A. Une preuve que v 6∈ A est un lequel A compare v
énoncé de la forme si l'étiquette d'un n÷ud est i , l'étiquette du ls gauche est
∃i ∈ [[1, n[[, A[i ] < v < A[i + 1] ou
l'indice du n÷ud avec lequel l'algorithme compare v si v < A[i ],
l'étiquette du ls droit est l'indice du n÷ud avec lequel
v < A[1] ou
l'algorithme compare v si v > A[i ].
[ ]<v
A n
Les feuilles de A sont étiquetées par les preuves que v 6∈ A.
Si v 6∈ A, un algorithme de comparaison ne peut s'arrêter que s'il
possède une preuve. (Cet arbre peut être étendu en rajoutant une feuille a chaque sommet
interne étiqueté par i . Cette feuille correspond au résultat v = A[i ].)
A. Duret-Lutz Algorithmique 82 / 96 A. Duret-Lutz Algorithmique 83 / 96

Arbre de décision pour une recherche par Rangs et médians

comparaison (2/2)
La complexité en pire cas de l'algorithme est la longueur de la 3 Tris comparatifs 4 Tris linéaires
branche la plus longue de cet arbre de décision. Dénition Tri par dénombrement
Supposons par l'absurde qu'il y ait (strictement) moins de n sommet Rappel des tris par insertion Tri par paquets
internes. Dans ce cas il existe un indice i ∈ [[1, n]] qui n'étiquette et fusion Mélange aléatoire
aucun n÷ud de l'arbre.
5
Tri par sélection
Imaginons deux tableaux A et A0 tels que ∀j 6= i , A[j ] = A0 [j ] 6= v et Tri par tas 6 Recherche dans un tableau trié
A[i ] = v et A [i ] 6= v .
0 Structure de tas

L'algorithme de comparaison (représenté par l'arbre de décision) ne Opérations sur le tas 7 Rangs et médians
peut distinguer ces deux tableaux, donc il donne un résultat incorrect. Tri rapide Minimum
Le nombre de n÷uds internes est donc supérieur à n. Tri introspectif Sélection
Bornes de complexité des Sélection stochastique
Le nombre de comparaisons eectuées dans le pire cas est donc tris comparatifs Sélection en O(n)
supérieur à blog nc.
On a prouvé T (n) = Ω(log n) en pire cas.
A. Duret-Lutz Algorithmique 84 / 96 A. Duret-Lutz Algorithmique 85 / 96
Recherche du minimum Sélection
Minimum(A)
1 min ← A[1]
2 for i ← 2 to length(A) do Problème de la sélection
3 if min > A[i ] then Entrée : Un ensemble A de n nombres distincts et un nombre
4 min ← A[i ] i ∈ [[1, n ]].

5 return min Sortie : L'élément x ∈ A qui est plus grand que i − 1 autres
On a T (n) = n − 1 = Θ(n) comparaisons. éléments de A exactement.
On en déduit que le problème de la recherche du miminum est en Peut être résolu en O(n log n)
O(n). Est-il possible de faire mieux ? Il sut de trier A et retourner A[i ].
La recherche du minimum peut être vu comme un tournoi, remporté
par le plus petit élément. Chaque comparaison est un match. Tout On peut mieux faire !
élément hormis le vainqueur perdra au moins un match. Il faudrait Le problème est en Θ(n).
donc n − 1 comparaisons pour trouver le minimum.
Le problème de la recherche du minimum est donc en Θ(n).
A. Duret-Lutz Algorithmique 86 / 96 A. Duret-Lutz Algorithmique 87 / 96

Sélection stochastique Sélection stochastique : cas moyen (1/4)

RandomizedSelection(A, l , r , i ) La partition coupe A[1..n] en A[1..i ] et A[i + 1..n] avec n − 1 choix
1 if l = r then return A[l ] possibles pour i .
2 m ← RandomizedPartition(A, l , r )
3 k ←m−l +1
4 if i ≤ k 1 n−1
X
5 then return RandomizedSelection(A, l , m, i ) ( )≤ max(T (i ), T (n − i )) + Θ(n)
− 1 i =1
T n

6 else return RandomizedSelection(A, m + 1, r , i − k )

n

n−1
Pire cas 1 X
≤ (max(i , n − i )) + Θ(n)
La partition crée systématiquement deux ensembles de taille 1 et n − 1 i =1
T

r − l , plus grand contenant l'élément recherché.

(
T (n ) = Θ(n ) + T (n − 1) = Θ(n ).
2
si i ≥ dn/2e
On a max(i , n − i ) =
i
Cependant aucune entrée ne donne à coup sûr ce pire cas.
n − i si i ≤ bn/2c
Cas favorable
T (n ) = Θ(n ) + T (9n /10). a = 1, b = 10/9. n =n .
log10/9 1 0 Si n est pair, tous les termes entre T (dn/2e) et T (n) apparaissent
Cas 3 du Th. général. La régularité est respectée, et T (n) = Θ(n). deux fois. Si n est impair, T (bn/2c) est seul en plus.
A. Duret-Lutz Algorithmique 88 / 96 A. Duret-Lutz Algorithmique 89 / 96
Sélection stochastique : cas moyen (2/4) Sélection stochastique : cas moyen (3/4)
Lemme n−1
n −1 X 3
2 X ≤ 2

8
k n
( )≤ ( ) + Θ(n)
−1
T n T i
n k =bn/2c
i =bn/2c
Preuve
n −1
X (n − 1 + bn/2c)(n − bn/2c) n
2
− n + bn/2c − bn/2c2
= =
2 2
k

On veut montrer que T (n) = O(n). On va faire une démonstration k =bn/2c

par récurrence. Le principe : Si n est pair :
On suppose que T (m) ≤ cm pour une constante c et pour tout 4n 2
− 4n + 2n − n 2 3n 2
− 2n 3n 2

m tel que n ≤ m < n avec un n choisi. (On peut choisir c et = = ≤

0

n aussi grands que l'on veut pour aider la preuve.)

0
0
8 8 8
On démontre T (n) ≤ cm. Si n est impair :
On en déduit T (n) ≤ cm pour tous les n > n si T (n) = O(1) 0
=
4n − 4n + 2(n − 1) − (n − 1)
2 2

=
3n 2
−3
≤
3n 2

pour n ≤ n . 0 8 8 8
A. Duret-Lutz Algorithmique 90 / 96 A. Duret-Lutz Algorithmique 91 / 96

Sélection stochastique : cas moyen (4/4) Sélection en O(n)

n −1
2 X
Selection :
( )≤ ( ) + Θ(n)
−1
T n T i
n
i =bn/2c Diviser les n éléments en bn/5c groupes de 5 éléments et un
On suppose T (i ) ≤ ci pour i ≤ n : groupe de n mod 5 éléments.
n −1 Calculer le médian de chaque groupe.
2 X 2c 3n 2
Appeler Selection récursivement pour trouver le médian des
( )≤ + Θ(n)T (n) ≤ + Θ(n)
n − 1 n − 1 8
T n ci

i =bn/ c 2 médians.
3cn(n − 1) + 3cn 3cn 3c (n − 1) + 3c Partitionner le tableau d'entrée autour du médian des médians
T (n ) ≤ + Θ(n) ≤
4(n − 1) 4
+
4(n − 1)
+ Θ(n) en utilisant une version modiée de Partition. Notons k le
cn 3c 3c  cn
 nombre d'éléments de la région inférieure.
T (n ) ≤ cn − + + + Θ(n) ≤ cn + Θ(n) −
4 4 4(n − 1) 4 Appeler Selection récursivement pour trouver le i plus petit e

élément de la région inférieure si i ≥ k , ou le (i − k ) plus petit e

c peut être choisi assez grand pour que cn /4 domine le Θ(n )

élément de la région supérieure si i > k .
T (n ) ≤ cn et on en déduit T (n) = O(n)
A. Duret-Lutz Algorithmique 92 / 96 A. Duret-Lutz Algorithmique 93 / 96
Sélection en O(n) : étude (1/2) Sélection en O(n) : étude (2/2)
T n ( )≤ Θ(n) + T (n /5) + Θ(n) + T (3n/4)
| {z } | {z } | {z } | {z }
calculs des dn/5e médians médian des médians partition sélection récursive

Sans le terme T (n/5) on pourrait appliquer le théorème général est

obtenir T (n) = O(n). On va montrer cette borne par récurrence :
On substitue cn à T (n) :

cn 3cn 19cn  cn

( ) ≤ Θ(n) + + = Θ(n) + ≤ cn + Θ(n) −
5 4 20 20
T n

À la louche... Au moins un quart des éléments sont plus petits que le c peut être choisi assez grand pour que cn domine le Θ(n)
20

médian et un quart des éléments sont plus grands. (On peut être plus ( ) ≤ cn
précis.) Dans le pire cas, la partition retourne donc un sous-tableau
T n

de n/4 éléments et un autre de 3n/4 éléments. Donc T (n) = O(n).

A. Duret-Lutz Algorithmique 94 / 96 A. Duret-Lutz Algorithmique 95 / 96

Conclusion sur la sélection

Question : Nous avons fait des groupes de 5 valeurs.

Aurions-nous pu faire des groupes de 3 ? Des groupes de 7 ?
L'algorithme de sélection en O(n) montre que ce problème est
en O(n). C'est intéressant théoriquement, mais en pratique il est
généralement plus rapide d'utiliser la sélection stochastique.

L'algorithme de sélection stochastique (en O(n )) peut être

2

modié à la manière du Tri Introspectif pour se transformer en

 médian des médians  sur les entrées qui posent problème.
(Cherchez  introselect  sur l'Internet.)

A. Duret-Lutz Algorithmique 96 / 96