informatique (MP2I/MPI) · Chapitre 5 · Application directe du cours
Renverser une liste : deux décompositions, deux complexités
Récursivité · niveau 2
Énoncé
Ces deux fonctions renversent une liste. Laquelle choisir, et de combien ?
(* A *) let rec renverse = function [] -> [] | x :: r -> renverse r @ [x]
(* B *) let renverse l =
let rec aux acc = function [] -> acc | x :: r -> aux (x :: acc) r in
aux [] lCorrigé
Mesuré, sur des listes d'entiers, les deux fonctions rendant toujours le même résultat :
n : 1000 2000 4000 8000 16000 32000
A (@ naif) : 0,008 s 0,033 s 0,138 s 0,607 s 2,884 s 15,195 s
B (accum.) : 0,000 s 0,000 s 0,000 s 0,000 s 0,000 s 0,001 sLe temps de A est multiplié par quand double : c'est la signature d'un coût quadratique. Celui de B double : coût linéaire.
L'explication tient dans le coût de @. L'opérateur de concaténation recopie son argument gauche : a @ b coûte . Dans A, l'appel de rang concatène une liste de longueur , d'où
qui est la première récurrence du cours, , et vaut .
Dans B, chaque élément est placé en tête de l'accumulateur en , une fois : . De plus l'appel est terminal, donc l'espace est au lieu de .
La leçon de méthode. Les deux fonctions ont la même « forme » récursive et le même variant ; elles diffèrent par le coût de l'opération de recollement. Quand on établit une récurrence de complexité, la question n'est jamais « combien d'appels ? » seulement, mais « combien d'appels, et que coûte ce que je fais autour ». C'est très exactement la différence entre les deuxième et troisième formes du cours.
