Université de Bordeaux Préparation à l’agrégation

Mathématiques 2021–2022

Mémento complexité
Rappel. Soit g une fonction strictement positive ; on écrit
• f = O(g) s’il existe C > 0 et x0 tel que f (x) 6 C · g(x) pour tout x > x0 .
 C
e
• f = O(g) s’il existe C > 0 et x0 tel que f (x) 6 g(x)· log g(x) pour tout x > x0 .

1. Tri
Le tri de n éléments s’effectue en utilisant O(n log n) comparaisons (tri fusion).

2. Exponentiation binaire
P
Le calcul de xn s’effectue en utilisant O(log n) multiplications (écriture de n = i6t ni 2i
i
en base 2 et calcul des x2 en utilisant t carrés successifs).

3. Dans Z
La taille (binaire) d’un entier a est le nombre de bits1 utilisé pour l’écrire, en d’autres termes
t(a) := ⌊log2 (|a| + 1)⌋ + 1. En général, a > 1 tend vers l’infini et on utilise simplement
log2 (a). On suppose que tous les opérandes sont de taille 6 n :
Opération Naïf Rapide
a+b O(n) O(n)
a × b O(n ) 2 e
MZ (n) = O(n)
a = bq + r O(n2 ) O(MZ (n))
Relation de Bézout O(n2 ) O(MZ (n) · log n)
Restes chinois O(n2 ) O(MZ (n) · log n)
Pour tous ces algorithmes, on compte le nombre d’opérations élémentaires sur les bits, sup-
posé proportionnel au temps d’exécution (complexité en temps). La complexité en espace
e
est de O(n) bits.
• Multiplication : MZ (n) est par définition le temps d’une multiplication dans Z
pour deux opérandes de taille 6 n. L’algorithme rapide (Harley et van der Hoeven,
2019), en temps O(n log n), utilise la Transformée de Fourier Discrète.
Moins rapide mais beaucoup plus simple : l’algorithme de Karatsuba utilise
O(nlog2 3 ) opérations.
Remarque. Pour des opérantes de tailles différentes, s(a) 6 n, s(b) 6 m, l’algo-
rithme naïf (quadratique) utilise O((n + 1)(m + 1)) opérations.
1Il
 
n’y a pas d’inconvénient à compter les chiffres en base β > 2, avec t(a) := logβ (|a| + 1) . Pas
vraiment d’intérêt théorique non plus.
1
2

• Division euclidienne : l’entrée est (a, b), b 6= 0, et la sortie (q, r) avec 0 6 r < |b|.
L’algorithme rapide résout l’équation b−a/x = 0 en utilisant l’itération de Newton

xn+1 = xn − xn (xn b − a) .

(Calcul effectué en doublant la précision à chaque étape ; soit dans un modèle

flottant, soit modulo 2k .) On pose q = ⌊x⌋, puis r = a−bq. L’énoncé de complexité
suppose que MZ (n) vérifie des propriétés du type M(n)/n > M(m)/m pour n > m,
et M(mn) 6 m2 M(n). Qui sont vraies aussi bien pour l’algorithme naïf que pour
Karatsuba ou Harley - van der Hoeven.
Remarque. Si t(a) 6 n, t(b) 6 m, n > m, l’algorithme naïf (quadratique) utilise
O((n − m + 1)(m + 1)) opérations élémentaires.
• Bézout : l’entrée est (a, b) et la sortie consiste en pgcd(a, b) et deux entiers u, v
tels que au + bv = gcd(a, b).
• Restes chinois : l’entrée consiste en N congruences x ≡ ak (mod bk ) où les bk sont
2 à 2 premiers entre eux, et la sortie attendue
P
est une solution de ce système de
congruences. On suppose t(ak ) 6 t(bk ) and k t(bk ) 6 n.

4. Dans Z/NZ
On choisit un représentant canonique dans chaque classe de congruence : les entiers de
[0, N − 1], pour représenter les éléments de Z/NZ. La taille des opérandes est 6 n := t(N).

L’addition est implantée comme une addition dans Z, suivie d’une (possible) soustraction :
temps O(n). La multiplication est une multiplication in Z, suivie par une division eucli-
dienne par N : temps O(n2 ) ou O(MZ (n)). L’inversion utilise une relation de Bézout :
temps O(n2 ) ou O(MZ (n) · log n).

5. Dans K[X], K un corps

La taille (algébrique) d’un polynône h ∈ K[X] est son nombre de coefficients : t(h) :=
deg h + 1 6 n.
Pour la complexité, on choisit de compter les opérations dans K (complexité algébrique) :
+, −, ×, / dans K. Pour estimer plus réalistement le temps de calcul, on peut multiplier
par le coût d’une opération élémentaire dans K quand celui-ci est borné uniformément
(c’est le cas si K est un corps fini) ; sinon il faut tenir compte de la taille des coefficients.
Soient f, g deux polynômes dans K[X], de tailles 6 n.
 3

Opération Naïf Rapide

f +g O(n) [+] O(n) [+]
2
f × g O(n ) [+, ×] e
MK[X] (n) = O(n)
f = gh + r O(n2 ) O(MK[X] (n))
Bézout O(n2 ) O(MK[X] (n) · log n)
Restes chinois O(n2 ) O(MK[X] (n) · log n)

6. Dans K[X]/(T ) :
Deux cas particuliers importants : définitions des corps finis non premiers Fq comme ex-
tension algébrique de Fp = Z/pZ et des extensions de Q (nombres algébriques). De façon
analogue à Z/NZ nous travaillons avec des polynômes de taille 6 t(T ), avec les coûts
ci-dessus. L’inversion utilise de nouveau une relation de Bézout.

7. Dans Mn×n (K) :

On se place de nouveau dans le modèle de complexité algébrique : on compte les opérations
dans le corps K. Pour A ∈ Mn×n (K), sa taille est t(A) = n2 ; pour v ∈ K n sa taille est
t(v) := n. On note A, B deux matrices dans Mn (K).
Opérations Naïf Rapide
A + B O(n2 ) O(n2 )
Av, v ∈ K n O(n2 ) O(n2 )
A × B O(n3 ) O(nω ), ω = 2.3729
A−1 O(n3 ) O(nω )
P A = LU O(n3 ) O(nω )
Char A O(n3 ) O(nω )
La factorisation LU (pivot de Gauss) permet de résoudre la plupart des problèmes d’algèbre
linéaire sur K : noyau, image, rang, déterminant, inverse, système linéaire (LU + résolution
de systèmes triangulaires en O(n2 ) opérations supplémentaires dans K).
La constante ω 6 3 qui apparaît ci-dessus est appelé exposant de la multiplication ma-
tricielle. La valeur utilisée en pratique (pour des matrices physiquement représentables par
les ordinateurs actuels) est ω = log2 7 ≈ 2.8 (Strassen).
Algèbre linéaire ✭✭ Boîte Noire ✮✮. Dans ce modèle, les coûts sont exprimés en terme du
nombre d’évaluations v 7→ A · v pour un “opérateur boîte noire” A. (Un opérateur linéaire
dont on ne suppose pas qu’il est donné par une matrice. On sait simplement calculer
l’image de tout vecteur v ∈ K n .) En général, une multiplication matrice-vecteur pour
A ∈ Mn×n (K) et v ∈ K n utilise O(n2 ) opérations dans K mais la plupart des matrices
rencontrées en pratique sont ✭✭ structurées ✮✮ et permettent une évaluation plus économique :
4

matrices par bandes, plus généralement matrices creuses (comme dans l’algorithme de
Dixon de factorisation dans Z) ; matrice de Sylvester définissant le résultant ; matrice de
Berlekamp (pour factoriser les polynômes sur les corps finis) ; matrices de van der Monde
(comme les matrices de FFT), etc.
Dans ce modèle il existe des algorithmes probabilistes (Lanczos, Wiedemann) qui ré-
solvent efficacement des problèmes d’algèbre linéaire comme le calcul du polynôme carac-
téristique ou du rang de A (avec faible probabilité d’erreur dans les 2 cas), ou trouve une
solution du système linéaire Ax = b. Ils utilisent en moyenne O(n) evaluations A · v, plus
O(n2 ) opérations dans K. On ne gagne rien sur une matrice dense générale (A · v utilise
O(n2 ) opérations dans K) ; mais le gain est significatif si A · v se calcule plus rapidement.