Notes de cours d’algorithmique

Gilles Zémor

Février 2021

1 Algorithmes gloutons

1.1 Principe général d’une démonstration qu’un algorithme

glouton est optimal
On prend une solution gloutonne g1 , g2 , . . . , gn , dans l’ordre du déroulement de l’al-
gorithme, que l’on compare à une solution optimale. On suppose que g1 , g2 , . . . , gm
font partie de la solution optimale O et l’on montre qu’il existe alors une solution
optimale O0 qui contient g1 , g2 , . . . , gm , gm+1 .

Exemple 1. On veut exprimer un entier positif S comme somme du plus petit

nombre possible de «pièces» appartenant à l’ensemble {20, 10, 5, 2, 1}. La solution
gloutonne consiste à choisir la pièce P la plus grande inférieure ou égale à S puis
à recommencer avec S ← S − P .
Considérons le premier moment où l’algorithme glouton diverge avec une solution
optimale. À ce moment il s’agit de reconstituer S. Supposons S > 20. La solution
gloutonne nous dit de choisir une pièce de 20. Puisque nous divergeons de la
solution optimale, c’est qu’il n’y a pas de pièce de 20 dans la solution optimale
O. On remarque qu’il ne peut y avoir au plus qu’une pièce de 10 dans la solution
optimale, car s’il y en a deux, on aurait une solution meilleure en remplaçant deux
pièces de 10 par une pièce de 20. De même il y a au plus une pièce de 5. Il peut y
avoir deux pièces de 2, mais pas 3, car 3 × 2 = 5 + 1. Enfin, il y a au plus une pièce
de 1. Mais l’ensemble de toutes les pièces autorisées ne somme qu’à 20 < S. Donc,
au moment où la solution gloutonne divergerait de la solution optimale on ne peut
qu’avoir S 6 20. Si S = 20 la solution est triviale et coïncide avec la gloutonne.
Enfin, pour S < 10 on peut raisonner de manière similaire à ci-dessus et conclure
que la solution gloutonne est toujours l’unique solution optimale.

1
Exemple 2 : recherche d’un stable maximum dans un graphe d’inter-
valles. On nous donne un ensemble I d’intervalles de la droite rélle, et on cherche
un ensemble maximum d’intervalles de I deux à deux disjoints. La solution glou-
tonne consiste à choisir, parmi les intervalles disjoints des intervalles déjà choisis,
l’intervalle [a, b] minimisant la valeur de b. Soit I1 , I2 , . . . , Im , Im+1 , . . . la solution
gloutonne, et supposons que I1 , I2 , . . . , Im , Jm+1 , Jm+2 , . . . est une solution opti-
male, où Im+1 = [am+1 , bm+1 ] ne fait pas partie de cette solution. L’intervalle doit
intersecter au moins un intervalle de la solution optimale O, sinon on pourrait
le rajouter à O et améliorer la solution. Comme Im+1 n’intersecte pas I1 , . . . Im ,
il doit intersecter un certain Ji , i > m. Or Im+1 est choisi de telle sorte que son
extrêmité droite bm+1 est inférieure à l’extrêmité droite de tous les Jj , j > m. Il
ne peut donc pas y avoir deux intervalles distincts Ji et Jj qui intersectent Im+1
sinon ces deux intervalles s’intersecteraient en bm+1 . On peut donc fabriquer une
nouvelle solution optimale, en enlevant de O l’unique intervalle Ji qui intersecte
Im+1 , et en le remplaçant par l’intervalle Im+1 . C’est une procédure d’échange. De
proche en proche on en déduit qu’il existe une solution optimale qui contient la
solution gloutonne et donc qui lui est égale.

Exemple 3 : recherche d’un arbre couvrant de poids minimum. Algo-

rithme de Kruskal. On nous donne un graphe pondéré (chaque arête a un
poids). On souhaite mettre en évidence un arbre couvrant de poids minimal. L’al-
gorithme de Kruskal est un algorithme glouton qui, à chaque étape choisit l’arête
(ou une arête) de poids minimum parmi les arêtes qui ne créent pas de cycle avec
le sous-ensemble d’arêtes déjà choisies. Montrons que cette procédure produit tou-
jours un arbre couvrant de poids minimal. Soient la suite d’arêtes g1 , g2 , . . . , gn−1
choisies de manière gloutonne, et soit g1 , g2 , . . . , gm , em+1 , . . . , en−1 un arbre cou-
vrant M de poids minimal qui ne comprend pas l’arête gm+1 mais contient les arêtes
g1 , . . . gm . Ajoutons l’arête gm+1 à l’arbre M . Cela créé un cycle C. Remarquons
que ce cycle doit contenir une arête ei , i > m, car g1 , g2 , . . . , gm , gm+1 ne contient
pas de cycle. Si l’on enlève l’arête ei de ce cycle, on recréé un arbre de nouveau. En
d’autres termes on créé un nouvel arbre à partir de M en échangeant les arêtes ei et
gm+1 . Forcément le poids de l’arête gm+1 est inférieur ou égal au poids de l’arête ei
par définition de la procédure gloutonne (sinon l’algorithme glouton aurait préféré
l’arête ei à l’arête gm+1 ). On a donc fabriqué un nouvel arbre couvrant de poids
minimum qui coïncide plus avec l’arbre glouton, et de proche en proche on obtient
que l’arbre glouton est un arbre couvrant de poids minimal.

2
1.2 Matroïdes
On appelle matroïde tout ensemble fini X muni d’un ensemble de parties I vérifiant
les propriétés suivantes :
— (hérédité) si A ∈ I et B ⊂ A, alors B ∈ I.
— (échange) si A, B ∈ I et |B| > |A|, alors il existe b ∈ B ⊂ A tel que
A ∪ {b} ∈ I.
Les éléments de I sont appelés les indépendants du matroïde. On appelle base d’un
matroïde tout indépendant maximal (qui n’est pas inclus dans un indépendant
de cardinalité strictement supérieure). La propriété d’échange implique clairement
que toutes les bases ont le même nombre d’éléments, c’est la dimension du ma-
troïde. Enfin on appelle circuit du matroïde, toute partie C de X non-indépendante
mimale, i.e. telle que C \ {c} ∈ I pour tout c ∈ C.
La notion de matroïde est une généralisation abstraite à la fois d’un graphe et
d’un espace vectoriel.

Exemples de matroïdes.
Matroïdes de cardinalité. X est un ensemble fini à n éléments et I est l’ensemble
des parties de X contenant au plus k éléments, pour k < n fixé.
Matroïdes graphiques. X est l’ensemble des arêtes d’un graphe fini G, et I est
constitué des ensembles d’arêtes qui ne contiennent pas de cycle.
Matroïdes vectoriels (ou linéaires). X est un ensemble fini de vecteurs d’un espace
vectoriel V , et I est constitué des ensembles de vecteurs de X linéairement indé-
pendants. Autrement dit, X est représentable par l’ensemble des colonnes d’une
certaine matrice, et les indépendants sont les ensembles de colonnes linéairement
indépendantes. Ce cas particulier est derrière la terminologie de «matroïde» et de
partie «indépendante». La notion de circuit est quand à elle empruntée au contexte
des graphes.
On peut montrer (exercice !) qu’un matroïde graphique est aussi un matroïde vec-
toriel. Il en est de même des matroïdes de cardinalité. Tous les matroïdes ne sont
pas représentables comme des matroïdes vectoriels.
Lemme 1. Soit A ∈ I un indépendant. Soit x ∈ X tel que {x} ∈ I et tel que
A ∪ {x} ne soit plus un indépendant. Soit C ⊂ A ∪ {x} un circuit et soit y 6= x un
élément du circuit. Alors A \ {y} ∪ {x} est un indépendant.

Preuve : Remarquons que le circuit C doit exister : si A ∪ {x} n’est pas un circuit,
c’est qu’il existe un a ∈ A tel que A \ {a} ∪ {x} n’est pas un indépendant. On
supprime alors a de A ∪ {x}, pour obtenir un nouvel ensemble non indépendant et

3
on recommence jusqu’à obtenir un circuit C. Ce circuit contient d’autres éléments
que x puisqu’on a supposé {x} indépendant. Soit donc y ∈ C \ {x}. Notons que
|C \ {y} ∪ {x}| = |C|. Si |A| > |C|, alors la propriété d’échange nous dit qu’on
peut ajouter un élément a de A à C \ {y} ∪ {x} et obtenir encore un indépendant.
L’élément a qu’on ajoute ne peut pas être égal à y car un indépendant ne peut
pas contenir C 6∈ I. Le même argument d’échange nous permet de continuer cette
procédure jusqu’à obtenir que A \ {y} ∪ {x} doit être un indépendant.

Algorithme glouton : recherche d’une base de poids minimal dans un

matroïde. Il nous est donné un matroïde (X, I) pondéré, c’est-à-dire que chaque
élément x ∈ X est
P muni d’un poids p(x). On cherche une base B de poids minimale,
i.e. minimisant b∈B p(b). L’algorithme glouton consiste à construire itérativement
la base B, en partant de B = ∅ et en l’augmentant d’un élément à chaque étape.
Chaque étape consiste à rajouter à B un élément b de poids minimal parmi ceux
tels que B∪{b} est un indépendant. On remarque que dans le cas où le matroïde est
un matroïde graphique, le problème est celui de la recherche d’un arbre couvrant
de poids minimal et l’algorithme est exactement l’algorithme de Kruskal.
Preuve d’optimalité de l’algorithme glouton. Soit g1 , g2 , . . . , gm , gm+1 , . . . , gk une
base G produite par l’algorithme glouton et soit g1 , . . . , gm , bm+1 , . . . , bk une base
B de poids minimal telle que gm ne figure pas parmi les éléments de B. Considérons
B ∪ {gm+1 } : comme cet ensemble ne peut pas être indépendant, il doit contenir un
circuit C (comme nous l’avons déjà remarqué, il suffit de supprimer des éléments de
B ∪ {bm+1 } jusqu’à obtenir un non-indépendant minimal). Ce circuit doit contenir
gm+1 (sinon on aurait C ⊂ B ce qui n’est pas possible puisque B est indépendant),
et aussi au moins un élément bi de B qui n’est pas dans {g1 , . . . , gm } (sinon on
aurait C ⊂ G). Le lemme 1 nous dit que B 0 = B \ {b} ∪ {gm+1 } est encore une
base. Comme bi est différent de g1 , . . . , gm , on a forcément que p(gm+1 ) 6 p(bi ),
sinon l’algorithme glouton aurait préféré bi à gm+1 , et B 0 doit être une base de
poids minimal. De proche en proche on obtient que la base gloutonne est une base
de poids minimal.

Matroïde transversal. Soit (X, Y, E) un graphe biparti, dont chaque arête

e ∈ E relie un sommet de X à un sommet de Y . Un couplage du graphe est un
sous-graphe de degré 1, c’est un dire un ensemble C ⊂ E d’arêtes reliant A ⊂ X
à A0 ⊂ Y de telle sorte que chaque a ∈ A et chaque a0 ∈ A0 est incident à une
unique arête de C.
On appelle transversal partiel de X une partie A ⊂ X pouvant être couplée à une
partie A0 ⊂ Y . Soit I l’ensemble des transversaux partiels de X.

4
Proposition 2. L’ensemble I munit X d’une structure de matroïde, appelé ma-
troïde transversal.

Preuve : La propriété d’hérédité est trivialement vérifiée, il s’agit donc de prouver

la propriété d’échange. Soit A, B ⊂ X des transversaux partiels, avec |B| > |A|.
Il s’agit de montrer qu’il existe b ∈ B \ A tel que A ∪ {b} puisse être couplé avec
une partie de Y .
Soit CA et CB les couplages issus de A et B respectivement. Considérons CA
comme un ensemble d’arêtes rouges et CB comme un ensembles d’arêtes bleues.
Réunissons les arêtes bleues et rouges pour former un graphe GAB . Notons que nous
distinguons toutes les arêtes bleues et rouges, c’est-à-dire que si une arête bleue
et une arête rouge sont issues de la même arête d’origine, elles deviennent deux
arêtes distinctes qui forment un cycle de longueur 2 dans GAB . Nous remarquons
que le graphe GAB est un graphe de degré maximum 2, et est donc constitué d’une
réunion disjointe de cycles et de chemins. Dans chaque cycle et chaque chemin, les
arêtes bleues et rouges alternent. Comme |B| > |A|, il y a strictement plus d’arêtes
bleues que d’arêtes rouges, et comme un cycle contient autant d’arêtes bleues que
d’arêtes rouges, il existe un chemin contenant strictement plus d’arêtes bleues
que d’arêtes rouges. Comme les arêtes bleues et rouges alternent sur ce chemin, il
comporte exactement une arête bleue de plus et ses deux extrémités sont incidentes
à des arêtes bleues. On constate que si dans le couplage CA on remplace les arêtes
rouges du chemin par les arêtes bleues on obtient un nouveau couplage constitué
d’une arête supplémentaire et qui couple A augmenté d’un élément de B à une
partie de Y . La situation est illustrée figure 1.

1.3 Algorithme de Huffman

L’algorithme de Huffman est un algorithme de compression. Le contexte est le
suivant. On suppose donnée une source, qui produit une suite X1 , X2 , . . . , XN de
symboles aléatoires chacun choisi parmi les symboles d’un même alphabet fini X =
{x1 , . . . , xm } et avec une même loi de probabilité p = (p1 , . . . , pm ), pi = P (Xj = xi )
pour tout j.
Un encodage de la source consiste à associer à chaque symbole xi ∈ X un mot d’un
code C constitué d’un ensemble de m mots. Une suite de symboles de la source est
ensuite transformée en la chaîne de bits obtenue par concaténation des encodages
des symboles successifs.
Exemple. Soit X = {1, 2, 3, 4} et soit X à valeurs dans X de loi p1 = 1/2, p2 =

5
 X Y

f f0

e e0

d d0

c
c0
b

a a0

Figure 1 – Exemple d’augmentation de couplage : A = {a, b, d, e} et B =

{a, c, d, e, f }. Le chemin alterné f, e0 , e, d0 , d, f 0 est celui qui permet d’augmenter le
transversal partiel A en A ∪ {f } par échange des arêtes rouges et bleues.

1/4, p3 = 1/8, p4 = 1/8 où pi = P (X = i). Soit le codage c défini par

c(1) =0
c(2) =10
c(3) =110
c(4) =111.

Le mot 011000101110 est l’encodage de la suite de symboles 1311241. Le code C

est un code dit préfixe, ce qui veut dire qu’aucun mot de C n’est le préfixe d’un
autre. Ceci permet de reconstituer sans ambiguïté la suite de symboles d’origine
à partir de son encodage par l’algorithme glouton consistant à lire la suite de bits
depuis la gauche et à lui associer un mot de code dès qu’on peut. Sur l’exemple,
comme le premier symbole 0 est un mot du code, on le prend, ensuite ni 1 ni 11 ne
sont dans le code, on continue donc à lire et on convertit 110 en «3» car 110 ∈ C,
et ainsi de suite.
Un code préfixe peut être utilement représenté par un arbre binaire dont les mots
du code sont les feuilles. Le code de l’exemple ci-dessus est ainsi représenté par
l’arbre de la figure 2.

6
 ∅

0 1

10 11

110 111

Figure 2 – L’arbre associé au code préfixe {0, 10, 110, 111}

Longueur moyenne d’un code. Appelons `i la longueur du mot binaire qui

encode le symbole xi . La longueur moyenne associée au code préfixe et à la loi de
probabilité p est
` = p1 `1 + · · · + pm `m
et représente le nombre de bits moyen représentant chaque symbole encodé.
Un code préfixe (ou un arbre) est dit optimal pour une loi p s’il minimise la longueur
moyenne `. L’algorithme de Huffman permet de construire un arbre optimal.

Algorithme de Huffman. A chaque étape on dispose d’un ensemble de sous-

arbres disjoints. La valeur de chaque sous-arbre est la somme des valeurs de ses
feuilles (une somme de pi ). Au début les sous-arbres sont juste m sommets uniques
associées aux valeurs p1 , . . . , pm . L’algorithme de Huffman est un algorithme glou-
ton qui à chaque étape réunit par un sommet père commun deux sous-arbres de
valeurs minimales. Au bout de m − 1 étapes on a donc fabriqué un arbre.
Exemple. Soit l’ensemble X = {x1 , x2 , . . . , x6 } et la loi p1 = 0.4, p2 = 0.04, p3 =
0.14, p4 = 0.18, p5 = 0.18, p6 = 0.06. L’arbre obtenu par l’algorithme de Huffman
est représenté sur la figure 3. La première étape consiste à joindre les sommets
terminaux (feuilles) x2 et x6 associés aux probabilités p2 et p6 les plus faibles et à
créer ainsi un sommet intermédiaire i de l’arbre associé à la probabilité pi = p2 +
p6 = 0.1. Puis on recommence la procédure sur l’ensemble X0 = {x1 , x3 , x4 , x5 , i}
pour la loi p1 = 0.4, p3 = 0.14, p4 = 0.18, p5 = 0.18, pi = 0.1. Les probabilités les
plus faibles sont p3 et pi , on joint donc x3 et i en un sommet père ii de probabilité
pii = 0.24. La procédure se termine par l’arbre de la figure 3.
Pour démontrer l’optimalité de l’algorithme de Huffman nous utiliserons le lemme
suivant.

7
 ∅

x1 iv
0.24 0.36

ii iii
0.1 0.14

i x3 x4 x5
0.04 0.06

x2 x6

Figure 3 – Arbre obtenu par application de l’algorithme de Huffman

Lemme 3. Soit l’ensemble X = {x1 , . . . , xm } et la loi p = (p1 , . . . , pm ) où l’on a

ordonné les xi de telle sorte que la suite des pi décroisse. Soit A un arbre optimal
pour la loi p.
— Chaque sommet de A qui n’est pas une feuille admet exactement deux som-
mets successeurs. En particulier il existe deux sommets de profondeur maxi-
male h ayant un même sommet père.
— Si deux feuilles de profondeur maximale et de même sommet père ne sont
pas étiquetées par xm et xm−1 , associées aux probabilités les plus faibles pm
et pm−1 , alors un échange d’étiquettes des feuilles permet d’avoir un autre
arbre optimal dont les deux feuilles considérées sont cette fois étiquetées par
xm et xm−1 .

Preuve : Si un sommet intermédiaire n’a qu’un successeur, alors on peut le sup-

primer et le remplacer par son successeur et faire diminuer strictement la longueur
moyenne. Ceci montre le premier point. Pour le deuxième point, si les étiquettes
des sommets considérés sont xi et xj , i, j 6= m, alors on peut clairement échan-
ger xi et xm sans augmenter la longueur moyenne de l’encodage. De même, si les
étiquettes des deux sommets sont xm et xi , i 6= m − 1, on peut échanger xi avec
xm−1 .

Optimalité de l’algorithme de Huffman. Soit H un arbre obtenu par l’algo-

rithme de Huffman et soit A un arbre optimal. Nous considérons A et H comme
des arbres étiquetés, où chacune des m feuilles est étiquetées par un pi et chaque
autre sommet est étiqueté par la somme des étiquettes de ses successeurs. Nous uti-

8
lisons la stratégie générale pour démontrer qu’un algorithme glouton est optimal,
c’est-à-dire que nous considérons la dernière étape e après laquelle l’algorithme de
Huffman produisant H est compatible avec l’arbre A. Ceci veut dire qu’à l’étape
e tous les sous-arbres disjoints de l’algorithme de Huffman sont aussi des sous-
arbres de A. Notons qu’au tout début de l’algorithme de Huffman (après l’étape
0), lorsque les sous-arbres sont des sommets uniques, ce sont tous des feuilles, donc
des sous-arbres de A. Soient s1 , . . . , sm−e les sommets racines des m−e sous-arbres
en question, communs à A et à H. Soit A0 le sous-arbre de A issu de sa racine
et ayant pour feuilles les sommets s1 , . . . sm−e . Soit p0 la loi p01 , . . . , p0m−e où p0j est
l’étiquette de s0j . Rappelons que la quantité `i = `i (A) pour l’arbre A désigne la
profondeur de la feuille étiquetée par le symbole xi . Nous constatons que la lon-
gueur moyenne ` pour l’arbre A et la loi p est égale à la longueur moyenne pour
l’arbre A0 et la loi p0 à laquelle il faut ajouter une quantité qui ne dépend que
des sous-arbres issus de s1 , . . . sm−e . L’arbre A0 est donc optimal pour la loi p0 .
Maintenant le lemme 3 nous permet d’affirmer qu’il existe une manière d’échanger
les étiquettes s1 , . . . , sm−e associées aux feuilles de A0 sans changer l’optimalité de
A0 et donc d’obtenir un nouvel arbre optimal pour la loi p qui coïncide avec l’arbre
de Huffman H jusqu’à l’étape e + 1. De proche en proche on obtient que l’arbre
de Huffman H est optimal.

2 Diviser pour reigner

Les algorithmes de type «diviser pour reigner» (divide and conquer) constitue une
famille d’algorithmes dont le principe général est de diviser le problème à traiter,
en sous-instances du problème d’origine de taille plus petite, qu’il s’agit ensuite
de recombiner. Quand l’algorithme s’appelle ainsi lui même sur une instance plus
petite, on dit qu’il est récursif.

Exemples.
Recherche dans une liste triée. Il nous est donnée une liste {a1 6 a2 6 · · · an } de
n entiers, triée dans l’ordre croissant, ainsi qu’un entier x dont on veut savoir s’il
est dans la liste. La recherche par dichotomie consiste à comparer x avec an/2 (en
supposant n pair), puis à répéter l’opération avec la première liste a1 . . . an/2−1 si
x < an/2 ou avec la deuxième liste an/2+1 , . . . , an si x > an/2 (si x = an/2 on a fini).
Si on note T (n) le temps de calcul nécessaire à l’execution de la tâche globale,
mesuré en le nombre nécessaire de comparaisons de x avec un entier de la liste, il
vient de la récursion l’inégalité :

T (n) 6 T (n/2) + 1. (1)

9
En réappliquant l’inégalité à la sous-liste de taille n/2 qui survit, on obtient T (n) 6
T (n/4) + 2, et de proche en proche T (n) 6 T (1) + n log2 n = n log2 n.
Tri. Il nous est donné cette fois-ci une liste a1 , a2 , . . . , an d’entiers dans un ordre
quelconque, et il s’agit de les trier. La méthode du tri fusion consiste à séparer
la liste en 2 parties d’égales longueurs (ou différent de 1 si n est impair), de trier
chacune des deux sous-listes, puis de les fusionner. Pour fusionner deux listes triées
de longueurs ` et `0 , on compare les deux plus petits éléments de chaque liste, et
on met le plus petit dans une troisième liste, puis on recommence avec les deux
listes initiales dont la somme des longueurs est devenue ` + `0 , jusqu’à ce que
la troisième liste contienne tous les ` + `0 éléments de manière ordonnée. Il faut
` + `0 − 1 comparaisons dans le pire cas pour faire la fusion. On a donc l’inégalité,
pour le nombre T (n) total de comparaisons d’entiers nécessaires au tri :
T (n) 6 2T (n/2) + n (2)
Si on réapplique cette inégalité aux sous-listes, il vient T (n) 6 4T (n/4) + n +
2(n/2) = 4T (n/4) + 2n, et de proche en proche :
T (n) 6 nT (n/n) + (log2 n)n = n log2 n
puisque T (1) = 0. On a supposé que n est une puissance de 2 pour simplifier, mais
le cas général est à peine différent.
Multiplication d’entiers. Soient deux entiers a et b de n bits au plus (< 2n , donc) à
multiplier. Supposons pour simplifier que n soit une puissance de 2. On peut écrire
a = a0 + a1 2n/2
b = b0 + b1 2n/2
où a0 , a1 , b0 , b1 sont tous des entiers d’au plus n/2 bits (< 2n/2 ). On a
ab = a0 b0 + (a1 b0 + a0 b1 )2n/2 + a1 b1 2n .
Ceci donne naissance à un algorithme récursif où il s’agit de faire quatre multipli-
cations d’entiers de n/2 bits, pour obtenir a0 b0 , a1 b0 , a0 b1 , a1 b1 , puis de faire des
additions d’entiers d’au plus 2n bits ainsi que des décalages (multiplications par
2n/2 et 2n ). Considérons que le coût d’une addition soit de l’ordre de grandeur de 2n
opérations élémentaires (addition de bits avec retenue), et écrivons donc l’inégalité
de récursion, sur le temps de calcul T (n) mesuré en opérations élémentaires :
T (n) 6 4T (n/2) + M n (3)
où M est une constante. Toujours en réappliquant l’inégalité, il vient T (n) 6
42 T (n/4) + M n + 4M n/2, et en itérant,
T (n) 6 4k T (n/2k ) + M (n + 4n/2 + · · · + 4k−1 n/2k−1 ),

10
ce qui, pour k = log2 n nous donne :

T (n) 6 4log2 n T (1) + M n(1 + 2 + 4 + · · · + 2k−1 )

= n2 + M n(2log2 n − 1)
6 n2 + M n 2 .

On retrouve donc la complexité de l’algorithme usuel de multiplication.

Multiplication de Karatsuba. On peut utiliser une astuce pour faire apparaître une
récursion différente. Remarquons que

a1 b0 + a0 b1 = (a0 + a1 )(b0 + b1 ) − a0 b0 − a1 b1 .

On peut donc obtenir le résultat en faisant appel à trois multiplications d’entiers

d’au plus n/2 + 1 bits, pour obtenir a0 b0 , a1 b1 , et (a0 + a1 )(b0 + b1 ). Il faut d’abord
avoir fait deux additions pour calculer (a0 + a1 ) et b0 + b1 : globalement, il faut
plus d’additions qu’avant, mais on a gagné sur le nombre de multiplications et
ceci est très intéressant car ces multiplications coûtent nettement plus cher que les
additions. On obtient la nouvelle inégalité récursive :

T (n) 6 3T (n/2) + O(n). (4)

À strictement parler, on a obtenu T (n) 6 2T (n/2) + T (n/2 + 1) + O(n). Mais on

peut écrire les deux entiers x et y de n/2 + 1 bits qu’il faut multiplier sous la forme
x = x0 + 2x1 et y = y0 + 2y1 , et comme les multiplications par un nombre de 1
bit ne coûtent rien, on voit que le coût d’une multiplication de deux nombres de
n/2 + 1 bits est au plus celui d’une multiplication de deux nombres de n/2 bits et
de quelques additions, ce qui justifie (4).
Il reste à déterminer la complexité asymptotique de la multiplication si on applique
cette méthode récursive. Plutôt que traiter chaque équation du type (1),(2),(3),(4)
au cas par cas, on comprend qu’il est utile d’avoir un théorème général.
Théorème 4. Si T (n) désigne le temps de calcul d’un algorithme récursif vérifiant
une inégalité du type T (n) 6 aT (dn/be)+O(nc ) pour des constantes a, c > 0, b > 1,
alors 
c
O(n )
 si c > logb a
T (n) 6 O(nc log n) si c = logb a

O(nlogb a ) si c < logb a.


Preuve : Supposons pour simplifier que n soit une puissance de b, n = bk , le cas

général n’étant pas fondamentalement différent. D’après l’hypothèse nous avons

T (n) 6 aT (n/b) + M nc (5)

11
pour tout n et pour une certaine constante M . En réappliquant (5) à n/b nous
avons :
 n  n c 
T (n) 6 a aT ( 2 ) + M + M nc
n b b
 a
6 a2 T 2 + M nc 1 + c
b b
et de proche en proche
n   a k−1 
k c a
T (n) 6 a T + Mn 1 + c + · · · + c .
bk b b

Prenons k = logb n et convenons que T (1) = 0 (sinon on peut appliquer la récursion

une fois de plus et convenir que T (1/b) = 0). On obtient :
  a logb n−1 
c a
T (n) 6 M n 1 + c + · · · + c .
b b

Si c > logb a, c’est-à-dire si a/bc < 1, la série converge et nous avons T (n) 6 O(nc ).
Si c = logb a, i.e. a/bc = 1, tous les termes de la série valent 1 et nous avons T (n) 6
M nc logb n. Enfin si c < logb a, i.e. a/bc > 1, nous obtenons T (n) 6 M 0 nc (a/bc )logb n
pour une constante M 0 , soit T (n) 6 M 0 alogb n = M 0 nlogb a .

12