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é :
On utilise les notations \(O(\;)\) pour estimer seulement le terme dominant de ces mesures.
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.
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\))
multiplication
complexité de la multiplication de deux entiers de \(n\) chiffres (resp. de deux polynômes de degré \(n\))
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)
multiplication dans \(M_n(K)\)
en termes d’opérations élémentaires de \(K\) (surtout multiplication)
Proposition
Note
un principe
Si on sait ramener un problème à un problème d’algèbre linéaire, on a «gagné».