Renverser une liste : deux décompositions, deux complexités

(* 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 [] l

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 s

Le temps de A est multiplié par $4$ quand $n$ 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 $\Theta (|a|)$. Dans A, l'appel de rang $k$ concatène une liste de longueur $n-k$, d'où

$$T(n)=T(n-1)+\Theta (n),$$

qui est la première récurrence du cours, $T(n)=T(n-1)+an$, et vaut $\Theta (n^2)$.

Dans B, chaque élément est placé en tête de l'accumulateur en $O(1)$, une fois : $T(n)=T(n-1)+O(1)=\Theta (n)$. De plus l'appel est terminal, donc l'espace est $O(1)$ au lieu de $\Theta (n)$.

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.