CHAPITRE 3 : L'ORDRE DE GRANDEUR : JETER CE QUI NE COMPTE PAS

Au chapitre précédent nous avons obtenu des comptes précis comme 4n² + 2n + 7. Nous allons maintenant en jeter presque tout, et voir pourquoi ce n'est pas de la paresse.

Regardons ce que chaque terme devient

Prenons T(n) = 4n² + 2n + 7 et calculons la part de chaque terme quand n grandit.

n	4n²	2n	7	part de 4n²
10	400	20	7	94 %
100	40 000	200	7	99,5 %
1 000	4 000 000	2 000	7	99,95 %
100 000	40 000 000 000	200 000	7	99,9995 %

À partir d'un millier d'éléments, les termes 2n et 7 pèsent moins d'un millième du total. Les garder, c'est noter les centimes sur une facture de plusieurs millions.

Quand n grandit, le terme qui grandit le plus vite finit par écraser tous les autres.

Premier geste : ne garder que le terme dominant

On ne conserve que le terme qui croît le plus vite.

4n² + 2n + 7        →  n²
3n + 100            →  n
n log n + 5n        →  n log n
2ⁿ + n¹⁰⁰           →  2ⁿ

La dernière ligne surprend toujours. n¹⁰⁰ paraît énorme, et il l'est : pour de petites valeurs. Mais 2ⁿ finit par le dépasser, et définitivement. L'ordre de grandeur ne s'intéresse qu'à ce qui se passe à la fin.

Second geste : jeter la constante multiplicative

De 4n² on ne garde que n². Ce coefficient 4 est le plus contesté des abandons, alors justifions-le.

Ce 4, d'où vient-il ? De notre façon de compter. Faut-il compter l'incrément de boucle ? Le test de fin ? L'accès au tableau comme une opération ou comme trois ? Selon la convention, le même code donne 3n², 4n² ou 6n².

Pire : ce coefficient change avec le compilateur, le processeur, le langage. C'est précisément la grandeur dont nous voulions nous débarrasser au chapitre 1. La garder reviendrait à réintroduire la machine dans une mesure censée en être indépendante.

Ce qu'on garde, en revanche, est solide : la forme de la montée. Doubler n multiplie le travail par 4, que le coefficient soit 3, 4 ou 100.

Ce qu'on perd, honnêtement. Deux algorithmes en n² dont l'un est dix fois plus rapide que l'autre reçoivent la même étiquette. La complexité ne dit pas tout : elle dit la chose la plus importante, pas toutes les choses. Pour départager deux algorithmes de même famille, il faut revenir à la mesure : cette fois à bon escient.

Le résultat

De T(n) = 4n² + 2n + 7, il reste n². On l'écrira O(n²), c'est l'objet du chapitre suivant.

Là où la simplification devient dangereuse

Trois situations où jeter les constantes conduit à se tromper.

1. Les données restent petites, pour toujours. Si vous triez toujours entre 5 et 20 éléments, le tri par insertion, O(n²), bat souvent le tri fusion : O(n log n). C'est d'ailleurs pour cela que les bibliothèques standard basculent sur un tri simple sous un certain seuil.

2. La constante est monstrueuse. Il existe des algorithmes de multiplication de matrices meilleurs que O(n³) sur le papier, dont la constante cachée est si grande qu'ils ne deviennent avantageux que pour des matrices plus grandes que toute mémoire disponible. On les appelle des algorithmes galactiques.

3. Toutes les opérations ne se valent pas. Lire en mémoire vive coûte une centaine de fois moins qu'un accès disque. Un algorithme en O(n) qui touche le disque à chaque pas sera plus lent qu'un O(n log n) qui reste en mémoire. Notre modèle fait semblant que toutes les opérations ont le même prix ; ce n'est vrai qu'en première approximation.

À retenir

On ne garde que le terme qui croît le plus vite, et on jette son coefficient.
Le coefficient dépend de la machine et de la façon de compter : c'est justement ce dont on voulait se débarrasser.
Ce qui reste, la forme de la montée, est vrai partout.
Sur de petites données, ou quand la constante est énorme, revenez à la mesure.

Exercices d'application

Exercice 1

Simplifiez : (a) 7n³ + 200n² + 50 000 (b) n + n log n (c) 2ⁿ + n⁵ (d) 100

Voir le corrigeMasquer le corrige

(a) n³. Le 50 000 impressionne, mais dès n = 50 le terme en n³ le dépasse, et ensuite l'écart ne fait que croître.

(b) n log n. Comme log n > 1 dès n ≥ 2, le terme n log n domine n.

(d) 1, autrement dit un coût constant : la valeur ne dépend pas de n.

Exercice 2

Un algorithme A fait 1 000n opérations, un algorithme B en fait n². À partir de quelle taille A devient-il meilleur ?

Voir le corrigeMasquer le corrige

On cherche le point où les deux comptes s'égalent :

1000 n = n²
1000   = n       (en divisant par n, qui est positif)

Jusqu'à n = 1 000, B est le meilleur. Au-delà, A prend l'avantage, et ne le rend plus.

Deux conclusions. D'abord, l'étiquette asymptotique a raison à la fin, pas tout de suite. Ensuite, si vos données ne dépassent jamais quelques centaines d'éléments, B est le bon choix, et la théorie ne le contredit pas, elle parle d'autre chose.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.