Une table de lignes, une autre de

Le calcul. La fusion naïve compare chaque ligne de la première à chaque ligne de la seconde :

$10000 \times 5000 = 50000000 comparaisons.$

La fusion indexée fait deux parcours : $5000$ insertions dans le dictionnaire, puis $10000$ recherches, soit

$10000 + 5000 = 15000 op e ˊ rations,$

parce qu'une recherche dans un dictionnaire ne dépend pas de sa taille (chapitre 5). Le rapport est de 3 333 : la version naïve fait plus de trois mille fois le travail de l'autre.

La mesure. On compte les opérations pour de vrai, sur des tailles doublantes, avec une seconde table deux fois plus courte.

$n$	naïve	rapport	indexée	rapport
$100$	$5000$	—	$150$	—
$200$	$20000$	$4, 0$	$300$	$2, 0$
$400$	$80000$	$4, 0$	$600$	$2, 0$
$800$	$320000$	$4, 0$	$1200$	$2, 0$

Les rapports confirment les deux lois. Quand $n$ double, la version naïve est multipliée par exactement $4 = 2^{2}$ : c'est la signature du coût quadratique. La version indexée est multipliée par $2$ : coût linéaire. Ce ne sont pas des approximations, ce sont les valeurs mesurées, parce que les deux compteurs sont exacts — $n \times n /2$ d'un côté, $n + n /2$ de l'autre.

Ce que le rapport permet. Mesurer un seul $n$ ne prouve rien : $5000$ pourrait être n'importe quoi. C'est la suite des rapports qui identifie la loi, et c'est pourquoi il faut toujours mesurer au moins trois tailles.

Énoncé

Corrigé