Probleme – De $\Theta (n^2)$ à $\Theta (n)$, et la mesure qui le confirme

1. L'algorithme naïf.

/* Renvoie la plus grande somme d'un segment de t[0..n-1]. Le segment
   vide etant admis, le resultat est toujours >= 0.
   Precondition : n >= 0. */
long max_segment_naif(const int t[], int n) {
    long meilleur = 0;
    for (int i = 0; i < n; i = i + 1) {
        long s = 0;
        for (int j = i; j < n; j = j + 1) {
            s = s + t[j];                        /* somme de t[i..j] */
            if (s > meilleur) { meilleur = s; }
        }
    }
    return meilleur;
}

Il examine les $n(n+1)/2$ segments, en temps constant chacun grâce à la somme accumulée : $\Theta (n^2)$ en temps, $\Theta (1)$ en espace. (Une version qui recalculerait chaque somme de zéro serait en $\Theta (n^3)$ — c'est la faute la plus fréquente sur cet exercice.)

2. L'algorithme en un parcours.

/* Meme specification. Complexite : Theta(n) en temps, Theta(1) en espace. */
long max_segment(const int t[], int n) {
    long meilleur = 0, courant = 0;
    /* INVARIANT (avant le tour i) :
         meilleur = plus grande somme d'un segment de t[0..i-1] ;
         courant  = plus grande somme d'un segment SE TERMINANT en i-1
                    (le segment vide comptant pour 0). */
    for (int i = 0; i < n; i = i + 1) {
        courant = courant + t[i];
        if (courant < 0) { courant = 0; }
        if (courant > meilleur) { meilleur = courant; }
    }
    return meilleur;
}

Correction. Initialisation : avant le tour $0$, les deux tranches sont vides et les deux variables valent $0$.

Conservation. Soit l'invariant vrai avant le tour $i$. Un segment se terminant en $i$ est, ou bien le segment vide (somme $0$), ou bien un segment se terminant en $i-1$ auquel on ajoute $t[i]$. Le meilleur de la seconde famille vaut donc $\text{courant}+t[i]$, et le meilleur des deux familles vaut $\max (0,\text{courant}+t[i])$ — précisément ce que calculent les deux premières lignes du corps. Ensuite, le meilleur segment de $t[\mathrm{0..}i]$ est ou bien inclus dans $t[\mathrm{0..}i-1]$ (valeur meilleur), ou bien se termine en $i$ (valeur courant recalculée) : le maximum des deux est ce que pose la troisième ligne.

Utilisation : à la sortie, $i=n$ et meilleur est la plus grande somme d'un segment de $t[\mathrm{0..}n-1]$. Terminaison : variant $n-i$.

Vérification. Sur $[-2,1,-3,4,-1,2,1,-5,4]$, les deux fonctions rendent $6$ — c'est le segment $[4,-1,2,1]$. Sur $[-3,-1,-7]$, les deux rendent $0$ : le segment vide, conformément à la spécification. Ce second cas est le test qui compte : c'est le seul endroit où une lecture distraite de l'invariant donne $-1$ au lieu de $0$.

3. La mesure.

    n | naif (ms) | Kadane (ms) | operations naif | operations Kadane
 1000 |     0,355 |     0,00103 |          500500 |              1000
 2000 |     1,414 |     0,00208 |         2001000 |              2000
 4000 |     5,656 |     0,00417 |         8002000 |              4000
 8000 |    22,531 |     0,00837 |        32004000 |              8000
16000 |    90,087 |     0,01676 |       128008000 |             16000

Les rapports de temps entre deux lignes consécutives :

Doubler $n$ multiplie l'un par $4$ et l'autre par $2$ : c'est la signature de $\Theta (n^2)$ et de $\Theta (n)$, lue directement sur les mesures. À $n=16000$, le rapport entre les deux programmes atteint $5400$.

4. Ce que la mesure prouve, et ce qu'elle ne prouve pas.

Elle prouve que la transcription est fidèle : si le code écrit ne réalisait pas l'algorithme analysé, les rapports ne seraient pas $4$ et $2$. C'est un contrôle puissant et rarement pratiqué — et c'est pourquoi il faut regarder les rapports et non les temps absolus, qui ne disent rien hors de cette machine.

Elle ne prouve pas que les fonctions sont correctes : elles pourraient rendre toutes deux la même valeur fausse, et les rapports seraient inchangés. Elle établit mal, aussi, la différence entre $\Theta (n)$ et $\Theta (n\log n)$ : un coût quasi-linéaire donnerait sur cette plage des rapports allant de $2,20$ à $2,15$, et il faut des mesures très propres pour les séparer de $2$. Les nôtres, à $2,00$ et $2,01$, y parviennent — mais de justesse, et une machine chargée aurait suffi à brouiller la conclusion. Seule la lecture du code établit qu'il y a une boucle et une seule.

Preuve et mesure ne se remplacent donc pas : la preuve dit ce que fait l'algorithme, la mesure dit que le programme est bien celui-là. C'est la répartition des rôles du chapitre chap:discipline, et elle vaut pour tout le livre.