Une ligne qui coûte un ordre de grandeur

List.length est en $\Theta (|a|)$ : elle parcourt. L'appeler à chaque prise d'un élément de droite transforme une fusion linéaire en fusion quadratique. Sur une liste strictement décroissante, où chaque prise vient de droite, la fusion de deux moitiés de taille $n/2$ coûte $\Theta (n^2)$, d'où

$$T(n)=2T(n/2)+\Theta (n^2)=\Theta (n^2),$$

et non $\Theta (n\log n)$.

La correction consiste à transporter la longueur au lieu de la recalculer — c'est une information que l'appelant possède déjà :

(* Renvoie (liste triée, longueur, nombre d'inversions).
   Précondition : couper_contigu sépare préfixe et suffixe (exercice précédent).
   Complexité : Theta(n log n) dans tous les cas. *)
let compte_inversions l0 =
  let rec aux l n =
    if n <= 1 then (l, 0)
    else
      let (g, d) = couper_contigu l in
      let ng = n / 2 in
      let (g', ig) = aux g ng and (d', id) = aux d (n - ng) in
      (* na est la longueur de a, transportée, jamais recalculée *)
      let rec fusion a na b =
        match a, b with
        | [], m -> (m, 0)
        | m, [] -> (m, 0)
        | x :: ra, y :: rb ->
            if x <= y then let (f, k) = fusion ra (na - 1) b in (x :: f, k)
            else let (f, k) = fusion a na rb in (y :: f, k + na)
      in
      let (f, i) = fusion g' ng d' in
      (f, ig + id + i)
  in snd (aux l0 (List.length l0))

La mesure — opérations comptées sur une liste strictement décroissante, le pire cas :

Les deux premières colonnes diffèrent exactement de $n(n-1)/2$ : $33664-1024=32640$, $528896-5120=523776$, $8411136-24576=8386560$. Ce n'est pas un hasard — chaque appel à List.length a coûte exactement le nombre d'inversions qu'il compte, et la somme de ces nombres est le nombre total d'inversions, ici $n(n-1)/2$. Le surcoût de la ligne fautive est le résultat qu'elle calcule. Et les temps, mesurés :

Quand $n$ double, la version lente est multipliée par $3,9$ — donc par $4$, la signature du quadratique — et la rapide par $2,0$.

Ce qu'il faut retenir. La complexité d'un algorithme n'est pas celle de son schéma : elle est celle de son code. Ici le schéma « diviser, régner, fusionner en temps linéaire » est parfaitement juste, et une seule ligne l'a démenti. La règle est la même qu'au chapitre chap:sequentielles : sur une liste chaînée, connaître la longueur est gratuit, la calculer est linéaire — et l'on ne calcule jamais dans une boucle ce qu'on peut transporter.