Complexité d’algorithmes

En algorithmique, il faut pouvoir mesurer la taille d’un objet et le nombre d’opérations élémentaires effectuées par un algorithme.

Ces notions se déclinent à plusieurs niveaux de granularité :

  • taille en nombre de bits, d’octets, en nombre de coefficients dans un anneau \(A\), en degré de polynôme…
  • complexité en nombre d’opérations sur un bit, en nombre d’additions ou de multiplications sur des entiers, en nombre d’opérations \(+,\times\) sur un anneau fixé…

On utilise les notations \(O(\;)\) pour estimer seulement le terme dominant de ces mesures.

Taille

  • Un entier \(N\) se représente en base \(b\) au moyen de \(n+1\) chiffres \(d_0,\dots d_n\in\set{0,b-1}\), où \(n=\floor{\log_b(N)}\).

    On dit qu’un entier inférieur à \(b^n\) est de taille \(O(n)\) (et le \(O\) ne dépend pas de la base).

  • Un polynôme de degré \(n\) se représente par \(n+1\) coefficients (ou par \(n\) évaluations et un coefficient dominant)

  • Un élément d’un corps fini \(\F_{p^n}\) se représente par une classe de \(\F_p[x]/(P)\), où \(P\in\F_p[x]\) est irréductible de degré \(n\), soit \(n\) entiers inférieurs à \(p\).

    La taille est donc \(O(n\log p)\).

  • Un ordinateur ne peut pas représenter un nombre réel. À la place, on travaille à précision fixée avec des approximations flottantes \(1,e_1e_2\dots e_n \times 2^e\), avec une mantisse de \(n\) bits et un exposant \(e\) entier.

    Attention, ce ne sont que des approximations de nombres réels, on a des problèmes d’erreurs d’arrondi qui se propagent quand on travaille avec.

  • Un élément d’un espace vectoriel de dimension \(n\) se représente par \(n\) coefficients (ex: polynômes, matrices, etc.)

  • Une matrice de \(M_n(A)\) se représente avec \(n^2\) coefficients de \(A\) : c’est la version pleine. Alternativement, si beaucoup de coefficients sont nuls, on peut la représenter de manière beaucoup plus économique par une liste de triplets (ligne, colonne, coefficient). C’est la version dite creuse.

    Idem avec les polynômes, surtout en plusieurs variables.

Addition et multiplication

Sans parallélisme, la complexité minimale de tout algorithme sur un entier de taille \(n\) est \(n\). Le seul fait de stocker ou de lire l’entier prend ce temps. Une opération élémentaire quand on travaille sur les entiers est une modification d’un bit (un processeur travaille en réalité par paquets de 32 ou 64 bits).

Un processeur fait de l’ordre d’un milliard d’opérations (additions, multiplications) sur des blocs de 32 ou 64 bits par seconde.

Remarque

cependant, tester la parité de \(n\) revient à n’en lire que le dernier bit, c’est assez indépendant de la taille de \(n\).

Soit \(P(x)\in A[x]\) un polynôme de degré \(n\) à coefficients dans un anneau \(A\). Une opération élémentaire relativement à \(A[X]\) est une opération \(+,-,\times\) de \(A\).

addition

complexité de l’addition de deux entiers de \(n\) chiffres (resp. de deux polynômes de \(A[x]\) degré \(n\)) en nombre d’opérations entre deux chiffres (resp. d’additions de \(A\))

  • méthode de primaire \(O(n)\)

multiplication

complexité de la multiplication de deux entiers de \(n\) chiffres (resp. de deux polynômes de degré \(n\))

  • algorithme naïf \(O(n^2)\)
  • décomposition de Karatsuba \(O(n^{1.58})\)
  • algorithme de Shönhage-Strassen (FFT) \(O(n\log(n)\log\log(n)^2)\)

Une fois qu’on sait additionner et multiplier les entiers, on sait aussi

  • prendre des puissances (exponentiation), voir tp.

    Il suffit de \(O(\log n)\) multiplications pour prendre une puissance \(n\).

  • diviser (algorithme de primaire ou voir tp)

  • calculer dans \(\Q\), dans \(\Z/n\Z\), dans \(\R\)

  • additionner et multiplier les matrices, les polynômes, les séries

  • calculer des pgcd, des relations de Bézout (voir tp Euclide)

  • calculer dans des quotients, des corps finis (voir tp corps finis)

Algèbre linéaire

multiplication dans \(M_n(K)\)

en termes d’opérations élémentaires de \(K\) (surtout multiplication)

  • algorithme naïf \(O(n^3)\)
  • décomposition de Strassen \(O(n^{2.81})\)

Proposition

  • déterminant, inversion \(O(n^3)\) (par pivot de Gauss)
  • polynôme caractéristique \(O(n^4)\) (méthode de Le Verrier ou Faddeev)
  • calculs d’image, de noyau, résolution de systèmes linéaires : tout est polynomial, avec des exposants raisonnables.

Note

un principe

Si on sait ramener un problème à un problème d’algèbre linéaire, on a «gagné».