Une table de lignes, une autre de

Exercice de TD · niveau 2 · NSI (première), chapitre 6 — Traiter des données en tables · Trier et fusionner

Énoncé

Une table de $10000$ lignes, une autre de $5000$ . Combien de comparaisons effectue une fusion qui, pour chaque ligne de la première, parcourt toute la seconde ? Et la version ci-dessus, qui construit d'abord un dictionnaire d'index ?

Corrigé

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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.