Leçon 926 : Analyse des algorithmes : Complexité.
Exemples.
Julie Parreaux
2018 - 2019
Références pour la leçon
[1] Beauquier, Berstel et Chretienne, Éléments d’algorithmique.
[2] Carton, Langages formels, calculabilité et complexité.
[3] Cormen, Algorithmique.
[4] Froidevaux, Gaudel et Soria, Types de données et algorithmes.
Développements de la leçon
Étude d’Union-Find pour la complexité Algorithme de Dijkstra
Plan de la leçon
1 Quantifier la complexité 2
1.1 Qu’est-ce que la complexité ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Mesurer la complexité [3, p.40] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Différentes approches de la complexité [4, p.19] . . . . . . . . . . . . . . . . . . . . 3
2 Techniques de calcul de la complexité 3
2.1 Le calcul direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 La résolution de récurrence [1, p.20] . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Le calcul de la complexité moyenne par l’espérance . . . . . . . . . . . . . . . . . 3
3 Raffinement de l’étude de la complexité : la complexité amortie 4
3.1 Méthode de l’agrégat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Méthode comptable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Méthode du potentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Amélioration de l’étude de la complexité 4
4.1 Borne minimale de la complexité sur une classe de problème . . . . . . . . . . . . 5
4.2 Utilisation de structures de données adaptées . . . . . . . . . . . . . . . . . . . . . 5
4.3 Compromis espace/temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Ouverture 5
1
Motivation
Défense
Lors de la conception, puis de l’étude d’un algorithme, deux notions sont extrêmement
importantes :
— la correction de l’algorithme : fait-il ce que l’on souhaite ?
— l’efficacité de l’algorithme : à quelle vitesse s’exécute-t-il ? ; est-il optimal ?
La complexité (temporelle ou spatiale) intervient alors pour comparer deux algorithmes cor-
rects répondant à la même question.
Ce qu’en dit le jury
Il s’agit ici d’une leçon d’exemples. Le candidat prendra soin de proposer l’analyse d’al-
gorithmes portant sur des domaines variés, avec des méthodes d’analyse également variées :
approche combinatoire ou probabiliste, analyse en moyenne ou dans le pire cas.
Si la complexité en temps est centrale dans la leçon, la complexité en espace ne doit pas être
négligée. La notion de complexité amortie a également toute sa place dans cette leçon, sur un
exemple bien choisi, comme union find (ce n’est qu’un exemple).
1 Quantifier la complexité
Définir la complexité d’un algorithme n’est pas facile. Intuitivement la complexité d’un al-
gorithme est un indicateur de la difficulté pour résoudre le problème traité par l’algorithme.
Mais cette vue de l’esprits n’est pas simple à quantifier. Nous allons alors définir la complexité
comme une fonction qui en fonction des entrées sur notre programme donnera la consomma-
tion d’une certaine ressource.
1.1 Qu’est-ce que la complexité ?
— Définition : donnée d’entrée d’un algorithme (= ensemble des variables externes à l’algo-
rithmes sur lesquelles on exécute celui-ci)
— Exemple : un algorithme de tri sur un tableau prend un tableau en entrée
— Définition : taille d’une entrée : f : {entree} → Nk
— Exemples : mot : nombre de caractère ; tableau : nombre de cellule ou l’espace mémoire
utilisé
— Définition : complexité comme fonction φ des entrées vers une ressources qui peut être
temporelle, spatiale, le nombre d’accès à un disque externe, ...
— Remarque : en pratique on compte des unités de bases (peut être des cellules mémoires,
des fonctions que l’on considère de bases)
n ( n −1)
— Exemples : complexité temporelle : tri bulle : 2 ; complexité disque dur : recherche
B-arbre h où h hauteur ; complexité temporelle : plus longue sous-séquence commune
1.2 Mesurer la complexité [3, p.40]
On ne peut pas toujours calculer la complexité exacte (avec les constantes) car générale-
ment, elle dépend de l’implémentation que nous utilisons. Pour cette même raison le calcul de
la complexité exacte peut s’avérer inutile.
2
— Définition Notation de Landau (O et Θ) + abus de notation
— Proposition : Équivalence des notations + illustration
— Exemples : Tri bulle O(n2 ) ; B-arbre O(log n)
— Proposition : L’ordre de croissance
1.3 Différentes approches de la complexité [4, p.19]
— Définition : Complexité pire cas, meilleur cas en moyenne (avec les probabilités)
— Remarque : Distribution uniforme : simplification de l’écriture mais pas toujours vrai At-
tention
— Définition : complexité constante
2 Techniques de calcul de la complexité
Maintenant que nous avons donné un cadre à notre théorie de la complexité, nous souhai-
tons calculer les complexités d’algorithmes usuels. Pour cela, nous allons présenter quelques
techniques de calcul élémentaires.
2.1 Le calcul direct
On peut parfois calculer directement la complexité en dénombrant les opérations que l’on
doit calculer. Efficace dans le cas d’algorithmes itératifs
Exemple : Recherche de maximum dans un tableau / CYK (Algorithme 1) O(n3 ) [2, p.198] /
Marche de Jarvis (Algorithme 2) O(hn) [1, p.389]
2.2 La résolution de récurrence [1, p.20]
On peut parfois exprimer la complexité pour une donnée de taille n par rapport à une
donnée de taille strictement inférieure. Résoudre l’équation ainsi obtenue nous donne la com-
plexité. Efficace dans le cas d’algorithmes récursifs.
— Proposition suite récurrente linéaire d’ordre 1 + Exemples Factorielle et Euclide
— Proposition suite récurrente linéaire d’ordre 2 + Exemple Fibonacci
— Proposition : Master theorem + Exemples Tri fusion et Strassen
— Remarque : Ne capture pas toutes les équations par récurrences.
2.3 Le calcul de la complexité moyenne par l’espérance
1
— Remarque : on a une distribution uniforme donc cmoy = | Dn | ∑ x ∈ Dn φ ( x )
— Exemple : tri rapide randomisé
— Remarque : on fait souvent l’hypothèse d’avoir une distribution uniforme sur les données
de l’entrée, cependant c’est généralement faux et cela nous introduit des erreurs.
3
3 Raffinement de l’étude de la complexité : la complexité amortie
La complexité amortie n’est pas une complexité moyenne ! La complexité amortie est une
amélioration de l’analyse dans le pire cas s’adaptant (ou calculant) aux besoins de performance
des structures de données.
c(opi )
— Définition : la complexité amortie : c amo = max ∑ik=1 k
op1 ,...,opk
— Exemple : table dynamique où on souhaite la complexité d’un élément qu’on insère en
nombre d’allocation et d’écriture [3, p.428]
3.1 Méthode de l’agrégat
Dans cette méthode, le coût amortie est le même pour toutes les opérations de la séquence
même si elle contient différentes opérations
— Principe : On calcul la complexité dans le pire cas pour cette séquence. La complexité
amortie d’une opération est donc cette complexité divisée par le nombre d’opérations de
la séquence [3, p.418].
— Exemples : table dynamique, Union find + Kruskal DEV, balayage de Gram
3.2 Méthode comptable
Cette méthode se différencie de la précédente en laissant la possibilité que toutes les opé-
rations ait un coup amortie différent.
— Principe : On attribut à chaque opération un crédit et une dépense (qui peuvent être
différent de leur coût réel). Ces crédits sont plus importants pour les opérations coû-
teuses afin de rattraper leur dépenses importantes. Cependant, elles doivent vérifier
la propriété suivante : ∑ik=1 cred(opi ) − ∑ik=1 dep(opi ) ≥ 0. On a alors : c amo (op) =
creel (op) + cred(op) − dep(op).
— Exemples : table dynamique, KMP
3.3 Méthode du potentiel
Cette méthode a été popularisé lors de la preuve de la complexité amortie de la structure
de données Union Find, implémentée à l’aide d’une forêt et des heuristiques qui vont bien.
Elle est moins facile que les autres à mettre en place.
— Principe : Au lieu d’assigner des crédits à des opérations, on va associer une éner-
gie potentielle ϕ à la structure elle-même. Cette énergie vérifie les propriétés sui-
vantes :ϕ(structure vide) = 0 et ∀ T, ϕ( T ) ≥ 0. On a alors c amo (op) = creel (op) + ϕ( T ) −
ϕ( T 0 ) lorsque l’opération op permet de passer de T à T 0 [3, p.424].
— Exemples : table dynamique
4 Amélioration de l’étude de la complexité
Plusieurs pistes existe afin d’améliorer la complexité d’un algorithme : utiliser une struc-
ture de données plus adaptée, utiliser un peu plus de mémoire ou au contraire se souvenir
de moins de choses, ... Cependant, quelques fois nous sommes capable de mettre une borne
minimale sur la complexité d’une famille de problème : quand nous avons atteint cette borne
on sait que nos algorithmes sont optimaux.
4
4.1 Borne minimale de la complexité sur une classe de problème
— Proposition : Borne minimal d’un algorithme de tri
— Exemple : Tri par insertion O(n2 ) ≥ O(n log n) ; Tri fusion O(n log n) atteint cette borne
— Remarque : même si on atteint la borne optimale asymptotique, on peut vouloir optimiser
les constantes (tri rapide est en moyenne plus rapide que le tri fusion).
4.2 Utilisation de structures de données adaptées
Une piste pour améliorer un algorithme : utiliser une bonne structure de données
— Exemple : tri par tas + Remarque : dépend de la manière dont on implémente la structure
— Exemple : représentation d’un graphe + Remarque : utilisation de ces représentation
— Exemple : Prim (liste d’adjacence) + Floyd Warshall (matrice d’adjacence)
— On peut changer de structure de données
— Exemple : Dijstra DEV
4.3 Compromis espace/temps
— Principe : On peut vouloir améliorer le temps au détriment de l’espace ou vise-versa.
— exemple : Fibonacci
— récursif : O(n2 ) en temps et O(1) en espace (amélioration de l’espace)
— programmation dynamique : O(n) pour le temps et l’espace (amélioration du
temps)
— utilisation de deux variables : O(n) pour le temps et O(1) pour l’espace (gagnant
sur les deux tableaux)
— Principe : le mémoïsation [3, p.338] + Exemple : découpage de barre
Ouverture
Évaluer la complexité d’un algorithme (hors implémentation) n’est pas une tâche facile.
Souvent plusieurs astuces sont nécessaire pour trouver la meilleure borne sur notre complexité
possible. Quelque fois, un approximation grossière de notre complexité (évaluation de la com-
plexité pour le tri par tas) suffit.
Quelques notions importantes
Notation de Landau
On ne peut pas toujours calculer la complexité exacte (avec les constantes) car générale-
ment, elle dépend de l’implémentation que nous utilisons. Pour cette même raison le calcul de
la complexité exacte peut s’avérer inutile. On quantifie alors la complexité asymptotiquement.
On utilise pour cela la notation de Landau [3, p.40].
Définition. Soit f , g : N → R+ . On note
O( g) = { f | ∃n0 , c ∈ N, ∀n ≥ n0 , 0 ≤ f (n) ≤ cg(n)} Majorant asymptotique
Θ( g) = { f | ∃n0 , c1 , c2 ∈ N, ∀n ≥ n0 , 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n)} Encadrement asymptotique
Ω( g) = { f | ∃n0 , c ∈ N, ∀n ≥ n0 , 0 ≤ cg(n) ≤ f (n)} Minorant asymptotique
5
Remarque (Abus de notation). On écrira f = O( g) (respectivement f = Θ( g)) pour f ∈ O( g)
(respectivement f ∈ Θ( g)).
Par définition, on a f = O( g) si et seulement si g = Ω( f ).
Proposition. Soient f , g : N → R+ , on a
[ f = O( g) et g = O( f )] ⇔ f = Θ( g)
g = Θ( f ) ⇔ f = Θ( g)
Par exemple, on a n2 + n = O(n3 ). De plus, n2 + n = O(n2 ) et n2 = O(n2 + n). Par la
proposition précédente, on a n2 + n = Θ(n2 ), mais n2 + n 6= Θ(n3 ).
Remarque. Ces notations sont transitives et réflexives.
Proposition. L’ordre de croissance des O est : O(1) ; O(log n) ; O(n) ; O(n log n) ; O(n2 ) ; O(nk ) ;
O(kn ) ; O(n!). Cet échelle de croissance est utile pour comparer l’efficacité de deux algorithmes corrects
résolvant le même problème.
Quelques analyses d’algorithmes
Nous donnons ici une liste d’exemples d’algorithmes pour lesquels nous calculons leur
complexité en mettant en place les différentes méthodes étudier dans la leçon sur la complexité.
Ce sont de bonnes illustrations du calcul de complexité.
L’algorithme Cocke–Younger–Kasami L’algorithme CYK (Cocke–Younger–Kasami) [2,
p.198] est un algorithme qui décide en temps cubique si un mot est engendré par une gram-
maire en forme normale quadratique. Il donne alors un certificat que tout langage algébrique
est dans la classe P : comme toute grammaire algébrique est équivalente à une grammaire en
forme normale quadratique, tout langage algébrique peut être décidé en temps cubique. Il faut
faire attention au fait que la grammaire est fixée et qu’elle ne fait pas partie de l’entrée car la
mise en forme normale d’une grammaire algébrique peut être exponentielle en sa taille.
Définition. Le problème du mot pour une grammaire algébrique :
entrée : une grammaire algébrique G = (Σ, T, R), w ∈ Σ∗ un mot
sortie : oui si w ∈ LG le langage engendré par G ; non sinon
Remarque : En général répondre à ce problème est coûteux O(|w|3 | G ||w| ).
Définition. Soit G une grammaire algébrique. On dit que :
— G est sous forme normale si les règles sont sous la forme A → BCD . . . Z où A ∈ T
(alphabet de travail) et B, . . . , Z ∈ Σ ∪ T.
— G est sous forme normale de Chomsky si les règles sont sous la forme : A → α pour,
A ∈ V, α ∈ Σ V ∩ Σ = ∅ ; S → e et A → BC pour A ∈ V et B, C ∈ V \ {S}
Théorème. Le problème du mot pour une grammaire algébrique sous forme forme normale de Chom-
sky est décidable et un algorithme de programmation dynamique le décide en temps O(|w|3 | G |) et en
mémoire O(|w|3 ).
Démonstration. Cet algorithme est un algorithme de programmation dynamique. Soit w =
a1 . . . an un mot.
6
On note : Algorithm 1 Algorithme CYk (Cocke–Younger–
— 1 ≤ i ≤ j ≤ n, w[i, j] = Kasami).
ai . . . a j 1: function CYK(w) . w = a1 . . . an : mot
2: for 1 ≤ i ≤ j ≤ n do . Initialisation ;
— 1 ≤ i ≤ j ≤ n,Ei,j =
Complexité : O(|w|2 ) (double boucle)
{S des variables telles quew[i, j] ∈
3: Ei,j ← ∅
LG (S)}. L’algorithme cal-
4: end for
cul tous ces Ei,j .
5: for i = 1 à n do . Cas i = j ; Complexité :
Nous allons maintenant énon- O(|w|| G |) (double boucle : une sur w, une sur G)
cer quelques propriétés d’appar- 6: for tout règle S → a do
tenance à ces ensembles Ei,j : 7: if ai = a then
— w ∈ LG (S0 ) si S0 ∈ E1,n 8: Ei,i ← Ei,i ∪ { a}
9: end if
— S appartient à Ei,i si et
10: end for
seulement si S → ai est une
11: end for
règle de G (w[i, i ] = ai et on
12: for d = 1 à n do . Cas i < j ; d = j − i ;
a une grammaire en forme 3
Complexité : O(|w| | G |) (triple boucle sur w ; une
normale quadratique)
sur G)
— S appartient à Ei,j (i < j) si 13: for i = 1 à n − d do
et seulement s’il existe une 14: for k = i à i + d do
règle S → S1 S2 et k ∈ N 15: for tout règle S → S1 S2 do
tels que w[i, k ] ∈ LG (S1 ) et 16: if S1 ∈ Ei,k et S2 ∈ Ek+1,i+d then
w[k + 1, j] ∈ LG (S2 ). 17: Ei,i+d ← Ei,i+d ∪ {S}
Les ensembles Ei,j peuvent être 18: end if
calculés à partir des ensembles 19: end for
Ei,k et Ek+1,j pour i ≤ k < j. 20: end for
L’algorithme les calcul par récur- 21: end for
rence sur la différence j − i. 22: end for
23: end function
Complexité : Comme la taille de la grammaire est fixé et ne fait pas partie de l’entrée (c’est
une constante), on a bien la complexité annoncé en O(|w|3 )
L’algorithme de la marche de Jarvis La marche de Jarvis [1, p.389] (ou algorithme du papier
cadeau) permet de calculer l’enveloppe convexe d’un ensemble de points. Le but de cet algo-
rithme n’est pas de déterminer les sommets de l’enveloppe convexe mais ces arêtes. Or [ p, q]
est une arête de l’enveloppe si et seulement si tous les points de l’ensemble sont du même
côté de la droite. On peut alors décider en temps O(n) si un segment est une arête de l’enve-
loppe. Comme on a O(n2 ) segment à examiner, on obtient une complexité en O(n3 ) pour cet
algorithme naïf.
La marche de Jarvis améliore cet algorithme en remarquant que le point suivant pk+1 d’une
enveloppe convexe est le point minimal dans l’ensemble pour l’ordre polaire relativement à la
droite [ pk , −−−→
pk−1 pk ). On obtient alors l’algorithme suivant :
Complexité : On a donc une complexité en O(hn) qui est intéressante si h est petit devant n
mais en O(n2 ) dans le pire cas.
L’algorithme du tri rapide randomisé Le tri rapide (Algorithme 3) est un tri en place dont la
complexité moyenne est en O(n log n) (elle est optimale) et dont la complexité au pire cas est en
O(n2 ). Il applique le paradigme diviser pour régner en séparant l’entrée en deux sous tableau
7
Algorithm 2 Algorithme calculant une enveloppe convexe par la marche de Jarvis.
1: function Jarvis(S) . S : ensemble des points
2: p1 le point d’ordonnée minimale de S (et d’abscisse si plusieurs) . Complexité : O(n)
−
→
3: p2 le point minimal de S \ { p1 } pour l’ordre polaire relativement à la droite [ pi , i ) .
Complexité : O(n)
4: k←2
5: while pk 6= p1 do . Complexité : O(h) où h est le nombre de points dans l’enveloppe
connexe
6: Calculer q le point minimal de S pour l’ordre polaire relativement à la droite
−−−→
[ p k , p k −1 p k ) . Complexité : O(n)
7: k ← k+1
8: pk ← q
9: end while
10: end function
dont les valeurs sont respectivement inférieures (ou supérieures) à un pivot. L’algorithme de
tri se rappelle alors sur ces deux sous tableau.
Algorithm 4 Algorithme du tri rapide ran-
Algorithm 3 Algorithme du tri rapide. domise.
1: function Tri-Rapide(A) . A : tableau 1: function Tri-Rapide(A) . A : tableau
à trier à trier
2: if [Link] ≥ 2 then 2: if [Link] ≥ 2 then
3: pivot ← A[0] 3: pivor ← Random( A) . On prend
4: i←0 un élément au hasard dans A
5: j ← [Link] − 1 4: i←0
6: while i < j do 5: j ← [Link] − 1
7: if A[i + 1] ≥ pivot then 6: while i < j do
8: Échanger A[i + 1] et A[ j] 7: if A[i + 1] ≥ pivot then
9: j ← j−1 8: Échanger A[i + 1] et A[ j]
10: else 9: j ← j−1
11: Échanger A[i + 1] et A[i ] 10: else
12: i ← i+1 11: Échanger A[i + 1] et A[i ]
13: end if 12: i ← i+1
14: end while 13: end if
15: Tri-Rapide( A[0 . . . i − 1]) 14: end while
16: Tri-Rapide( A[i + 1 . . . [Link] − 15: Tri-Rapide( A[0 . . . i − 1])
1]) 16: Tri-Rapide( A[i + 1 . . . [Link] −
17: end if 1])
18: end function 17: end if
18: end function
Théorème (Correction). L’algorithme du tri rapide (Algorithme 3) est correct.
Démonstration. content...
Analyse de la complexité du tri rapide
— Dans le pire cas :
— Dans le cas favorable
8
Remarque. L’équilibre du découpage du tableau en deux sous tableau se répercute dans la
complexité d’exécution.
Tri rapide randomisé Pour étudier la complexité moyenne de ce tri, nous allons utili-
ser une version randomisé qui simplifiera notre étude (Algorithme 4). On remarque que la
correction du nouvel algorithme ne change pas car elle ne dépend pas du pivot choisi mais
uniquement des actions autour de celui-ci.
L’algorithme du balayage de Graham Le balayage de Graham résout le problème de l’en-
veloppe connexe en conservant une pile de candidat aux sommets de cette dite enveloppe [3,
p.948]. Chacun des points est empiler une fois, puis tous ceux qui ne sont pas un sommet de
l’enveloppe seront dépilé. L’algorithme utilise deux sous-fonctions sommet qui retourne le haut
de la pile sans le modifier et sous-sommet qui retourne le deuxième élément de la pile sans la
modifier.
Algorithm 5 Algorithme calculant une enveloppe convexe par le balayage de Graham.
1: function Graham(S) . S : ensemble des points
2: p0 le point d’ordonnée minimale de S (et d’abscisse si plusieurs)
3: p1 , . . . , pm les points de S triés par angle polaire relativement à p0 (si égalité, on garde
le plus loin)
4: P←∅ . P est une pile
5: Empiler( p0 , P)
6: Empiler( p1 , P)
7: Empiler( p2 , P)
8: for i = 3 à m do
9: while l’angle formé les les points sous-sommet( P), sommet( P) et pi fond un tour à
gauche do
10: Dépiler( P)
11: end while
12: Empiler( pi , P)
13: end for
14: end function
Théorème (Correction). Si Graham est exécuter sur un ensemble S de points tel que |S| ≥ 3, alors, à
la fin de la procédure la pile P contient les du bas vers le haut les sommets de l’enveloppe convexe pris
dans l’ordre inverse des aiguilles d’une montre.
Arguments de la preuve. — Les points qui sont retire lors du tri ne sont pas dans l’enveloppe
convexe.
— Invariant : "A chaque itération de la boucle Pour, la pile P devient de bas en haut, les som-
mets de l’enveloppe convexe Qi−1 pris dans l’ordre inverse des aiguilles d’une montre."
où Qi est l’ensemble des i premiers éléments donné par le tri.
Initialisation La pile contient Q2 (trois points) qui sont bien leur enveloppe connexe pris
dans l’ordre inverse des aiguilles d’une montre.
Conservation Après la boucle tant que on fait apparaître l’invariant de l’itération précé-
dente (la pile contient la même chose). On montre ensuite que l’enveloppe convexe
de Q j ∪ { pi } est la même que celle de Qi soit pi en fait partie, soit il est à l’intérieur.
Terminaison Ok
9
Théorème (Complexité). Le temps d’exécution de Graham est O(n log n) si n = |S|.
Arguments de la preuve. — Choisir le point minimal Θ(n)
— Trier les autres points O(n log n) (si on utilise un algorithme de tri optimal (tri fusion ou
tri par tas) et la suppression des points d’angles polaires égaux se fait en O(n))
— La boucle pour nécessite un temps en O(n) sans compter la boucle tant que.
— La boucle tant que nécessite au total (pour n boucle pour) un temps en O(n). On utilise la
méthode de l’agrégat.
— On empile au plus un fois chaque points de S
— On dépile au plus autant que l’on empile : au plus m − 2 opérations de dépiler.
— Le test et l’opération de dépiler en O(1).
L’algorithme de Knuth–Morris–Pratt Les algorithmes Morris–Pratt et Knuth–Morris–Pratt
sont des algorithmes qui utilisent la notion de bord. On utilise le bord des préfixes du motif
pour être plus astucieux et rapide quand une comparaison échoue : il nous donne le décalage
que l’on doit réaliser.
Hypothèse : Le motif est fixe et connu à l’avance.
Quelques notions sur le bord [1, p.340] Le bord a un rôle essentiel dans ces algorithmes :
il permet de calculer le décalage que l’on va effectuer lors d’un échec de comparaison. Bien
définir cette notion est donc primordiale.
Définition. Un bord de x est un mot distinct de x qui est à la fois préfixe et suffixe de x. On
note Bord( x ) le bord maximal d’un mot non vide.
Exemple Le mot ababa possède les trois bords e, a et aba. De plus Bord( ababa) = aba.
Proposition. Soit x un mot non vide et k ∈ N, le plus petit, tel que Bordk ( x ) = e.
1. Les bords de x sont les mots Bordi ( x ) pour tout i ∈ {1, . . . , k }.
2. Soit a une lettre. Alors, Bord( xa) est le plus long préfixe de x qui est dans l’ensemble
{ Bord( x ) a, . . . Bord( x )k a, e}.
Arguments de la preuve. 1. z est un bord de Bord( x ) ssi z est un bord de x (+ récurrence).
2. z est un bord de za ssi z = e ou z = z0 a avec z0 un bord de x.
Corollaire. Soit x un mot non vide et soit a une lettre. Alors,
Bord( x ) a si Bord( x ) a est préfixe de x
Bord( xa) =
Bord( Bord( x ) a) sinon
Arguments de la preuve. — Si Bord( x ) a est préfixe de x alors Bord( x ) a = Bord( xa).
— Sinon, Bord( xa) est préfixe de Bord( x ) = y et le plus long préfixe de x dans { Bord(y) a, . . . Bord(y)k a, e}.
Définition. Soit x un mot de longueur m. On pose β : {0, . . . , m} → {−1, . . . , m − 1} la fonction
qui est définie comme suit : β(0) = −1 et pour tout i > 0, β(i ) = | Bord( x1 , . . . , xi )|. On
pose s : {1, . . . , m − 1} → {0, . . . , m} la fonction suppléance de x définie comme suit : s(i ) =
1 + β(i − 1), ∀i ∈ {1, . . . , m}.
10
Remarque : on a bien entendu β(i ) ≤ i − 1.
Corollaire. oit x un mot non vide de longueur m. Pour j ∈ {0, . . . , m − 1}, on a β(1 + j) = 1 + βk ( j)
où k ≥ 1 est le plus petit entier vérifiant l’une des deux conditions suivantes :
1. 1 + βk ( j) = 0
2. 1 + βk ( j) 6= 0 et x1+ βk ( j) = x j+1
Arguments de la preuve. Algorithme 6
Algorithm 6 Calcul de la fonction β don- Algorithm 7 Calcul de la fonction sup-
nant la taille des bords maximaux d’un mot pléance s du mot x.
x.
1: function S UPPLÉANCE(x, s) . x mot de
1: function B ORD -M AXIMAUX(x, β) .x
mot de taille m taille m
2: β [0] ← −1 2: s [1] ← 0
3: for j = 1 à m do 3: for j = 1 à m − 1 do
4: i ← β [ j − 1] 4: i ← s[ j]
5: while i ≥ 0 et x [ j] 6= x [i + 1] do 5: while i ≥ 0 et x [ j] 6= x [i ] do
6: i ← β [i ] 6: i ← s [i ]
7: end while 7: end while
8: β[ j] ← i + 1 8: s [ j + 1] ← i + 1
9: end for 9: end for
10: end function
10: end function
L’algorithme de Morris–Pratt [3, p.916] L’algorithme de Morris–Pratt utilise un automate
des occurrences pour calculer les bords du motif. On définit l’automate des occurrences associé
à P[1 . . . m] comme suit : Q = {1, . . . m} ; q0 = 0 ; F = {m} ; δ(q, a) = σ( Pq a) pour tout a ∈ Σ et
q ∈ Q.
Définition. La fonction suffixe associé au motif P σ : Σ∗ 7→ {0, 1, . . . , m} donne la longueur de
Bord( x ) pour x ∈ Σ∗ .
Complexité temporelle du prétraitement dans le
pire cas : O( p|Σ|) Ce fait une fois par motif.
Algorithm 8 Calcul de la fonction de tran-
sition δ de l’automate des occurrences. Algorithm 9 Calcul de la recherche dans
1: function C ALCUL -δ(P, Σ) . P motif ; Σ
l’automate des occurrences.
alphabet 1: function M ORRIS –P RATT (T, δ, p) .
2: p ← [Link] T texte ; δ fonction transition ; p la lon-
3: for q = 0 à p do gueur du motif
4: for a ∈ Σ do 2: t ← [Link]
5: k ← min( p + 1, q + 2) 3: for i = 1 à t do
6: repeat 4: q ← δ(q, T [i ])
7: k ← k+1 5: if q = p then
8: until Pk préfixe de Pq a . Pq 6: Retourner i − m
est le préfixe de P de longueur q. 7: end if
9: δ(q, a) ← k 8: end for
10: end for 9: Retourner 0
11: end for 10: end function
12: Retourner δ
13: end function
Complexité temporelle dans le pire cas : Θ(t)
11
Remarque : La validité de cet algorithme provient de la validité de la construction de l’auto-
mate des occurrences.
L’algorithme de Knuth–Morris–Pratt [1, p.343] Cet algorithme utilise une méthode plus
astucieuse afin de calculer les bords du préfixes. On s’épargne ainsi un calcul de l’automate
des occurrences et on calcul la fonction δ puisse à la volée. On exploite les propriétés de la
fonction de bord.
Définition. La fonction préfixe associé au motif P π : {1, 2, . . . , p} 7→ {0, 1, . . . , p − 1} donne
la longueur du plus long préfixe de P qui est suffixe propre de Pq où q ∈ {1, 2, . . . , p}.
Si on ne fait pas l’hypothèse d’un préfixe propre alors le plus long suffixe d’un mot qui est
aussi son préfixe est le mot en question. De plus, sans cette hypothèse l’algorithme de Knuth-
Morris-Pratt serait soit incorrect soit non terminal.
Algorithm 10 Algorithme de Knuth– Remarque : La validité de l’algorithme de
Morris–Pratt. Knuth–Morris–Pratt (Algorithme 10) pro-
1: function KMP(T, P) . T texte ; P motif vient des propriétés sur le bord.
2: t ← [Link] Complexité du prétraitement Calcul de la fonc-
3: p ← [Link] tion suppléance s : Θ( p) On applique une
4: i←1 méthode de l’agrégat : dans la boucle pour
5: j←1 la variable ne peut augmenter plus de p fois
6: s ← S UPPLÉANCE ( x, P) et comme elle est toujours strictement posi-
7: while i ≤ p et j ≤ t do tive, la boucle tant que ne peut pas s’exécu-
8: if i ≥ 1 et t[ j] 6= x [i ] then ter plus de p fois.
9: i ← s [i ] Complexité : Θ(t) On applique une méthode
10: else de l’agrégat (exactement le même raisonne-
11: i ← i+1 ment).
12: j ← j+1 Remarque : Il existe encore une version amé-
13: end if liorer de cet algorithme qui consiste à ne
14: end while pas vouloir se retrouver dans la même
15: if theni > m situation qu’au début (on teste toujours
16: Renvoie j − m une situation différente). Cette améliora-
17: else tion donne les même complexité asympto-
18: Renvoie 0 tique mais semblerait plus rapide en pra-
19: end if tique.
20: end function
L’exemple d’une table dynamique Lorsqu’on manipule un tableau [3, p.428], on ne connaît
pas toujours la place dont on va avoir besoin. On veut alors pouvoir ré-allouer une table plus
grande dans le cas où on ajoute une nouvelle valeur et que notre table est déjà pleine. Nous al-
lons montre que la complexité amortie de l’opération insérer est en O(1) lorsque insérer consiste
à ajouter l’élément dans la table si elle est non pleine ou de créer une table de taille double, de
recopier les valeurs de la première dans la nouvelle et d’ajouter la valeur dans cette table.
Analysons la complexité d’une séquence de n opérations insérer sur une table vide. On note
ci le coût de la iième opération. Si la table n’est pas pleine, on a ci = 1 sinon ci = i. Si on
effectue n opérations insérer, le coût défavorable d’une opération est O(n), ce qui donne une
complexité en O(n2 ) pour la séquence. Cette borne n’est pas optimale, on va calculer cette
complexité amortie, à l’aide des trois méthodes exposées dans la leçon.
12
Calcul par la méthode de l’agrégat On se donne une séquence de n opérations insérer sur
une table vide. On souhaite affiner la borne précédente. On remarque que la iième opération
déclenche une extension si et seulement si i − 1 est une puissance de deux. Le coût de la iième
opération est alors :
i si i − 1 est une puissance de 2
ci =
1 sinon
Le coût total de n opération insérer sur une table vide est :
n blog nc
∑ ci ≤ n + ∑ 2 j < n + 2n = 3n
i =1 j =1
Le coût amorti d’une opération insérer est au plus trois.
Calcul par la méthode comptable La méthode comptable permet de donner l’intuition de la
valeur trois. En effet, lorsqu’on insère un élément, on lui donne un crédit correspondant à son
insertion, son mouvement et la recopie d’un élément présent dans le tableau avant lui (comme
on double la taille du tableau le nombre d’éléments qui ne viennent pas d’être ajouté à déplacer
lorsque le tableau est plein est la moitié. Donc les ajouts financent bien la recopie des autres
éléments). Plus formellement, on fixe :
T est non plein cred(op) = 2 dep(op) = 0
T est plein cred(op) = 2 dep(op) = | T |
Ce qui nous donne
1+2−0
c amo (op) = =3
(| T | + 1) + 2 − | T |
D’où la complexité amortie de trois.
Calcul par la méthode du potentiel On va maintenant appliquer la méthode du potentiel
pour le calcul de cette complexité amortie. On souhaite une fonction potentielle qui vaut 0
lorsque la table vient d’être étendu et qui vaut la taille de la table lorsque celle-ci est pleine. La
fonction ϕ( T ) = [Link] − [Link] où [Link] est le nombre d’élément dans la table et [Link]
est sa taille, est une possibilité. On considère la iième opération. On distingue deux cas.
— Si elle ne déclenche pas d’extension de la table, alors taillei = taillei−1 et
c amo (i ) = ci + ϕi − ϕi−1 = 1 + (2numi − taillei ) − (2numi−1 − taillei−1 )
= 1 + (2numi − taillei ) − (2(numi − 1) − taillei ) = 3
— Si elle déclenche l’extension de la table, alors taillei = 2taillei−1 , taillei−1 = 2(numi ) − 1
et
c amo (i ) = ci + ϕi − ϕi−1 = 1 + (2numi − taillei ) − (2numi−1 − taillei−1 )
= 1 + (2numi − taillei ) − (2(numi − 1) − (numi − 1)) = 3
Analyse de relation par récurrence
Nous allons maintenant étudier comment résoudre des récurrences [4, p.536]. Nous ne
sommes pas obligé de tous détailler dans la leçon, mais en connaître quelques un peut être une
bonne chose.
13
Les types d’équations récurrentes On peut classifier les suites récurrentes en plusieurs
grandes familles :
— Les récurrences linéaires d’ordre k sont des équations du type : T (n) = f (n, T (n −
1), . . . , T (n − k)) + g(n) où k ∈ N est fixé, f est une combinaison linéaire de ces éléments
et g est une fonction quelconque. (Exemple : factorielle)
— Les récurrences de partitions sont des équations du type : T (n) = aT nb + d(n) où
a, b ∈ N sont des constantes, d est une fonction quelconque et n est une puissance de d.
(Elles apparaissent dans des algorithmes de partitions. Master theorem)
— Les récurrences complètes, linéaires ou polynomiales sont des équations du type :
T (n) = f (n, T (n − 1), . . . , T (0)) + g(n) où k ∈ N est fixé, f est une fonction linéaire
ou polynomiale et g est une fonction quelconque.
Il existe de nombreuses méthodes (de la méthode du calcul à la main aux séries génératrices)
pour résoudre ces équations. Nous allons donner l’exemple des récurrences linéaires d’ordre
1 et du master theorem.
Équations récurrentes linéaires d’ordre 1 On commence par les plus simple qui peuvent
généralement être résolue à la main. Nous allons donner un résultat sur ces équations.
Proposition. Pour une suite récurrente linéaire d’ordre 1 (un )n∈N avec un+1 = aun + b pour tout
n ≥ 0 où u0 ∈ R et a, b ∈ R. Alors un = an (u0 − l ) + l où l = 1−b a si a 6= 1 et un = bn + u0 sinon.
Pour l’algorithme calculant la factorielle, si on compte le nombre de multiplication, on a
une complexité en c(n) = c(n − 1) + 1 avec a = b = 1 et c(0) = 0. Donc c(n) = 1 ∗ n + 0 = n.
Références
[1] D. Beauquier, J. Berstel, and P. Chrétienne. Eléments d’algorithmique. Manuels informatiques
Masson. Masson, 1992.
[2] O. Carton. Langages formels, calculabilité et complexité. Vuibert, 2008.
[3] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Algorithmique, 3ème édition. Dunod, 2010.
[4] C. Froidevaux, M.C. Gaudel, and M. Soria. Types de données et algorithmes. McGraw-Hill,
1990.
14
