Sous-tableau de somme maximum : trois algorithmes

Complexité des programmes · niveau 2

Énoncé

On cherche la somme maximum d'un sous-tableau de $T [0 : n]$ (chapitre 11), le sous-tableau vide étant de somme $0$ .

Écrire un programme qui calcule la somme de chaque sous-tableau $T [d : f]$ par une boucle sur $[d : f]$ . Donner le nombre exact d'additions.
Améliorer le programme en remarquant que la somme de $T [d : f + 1]$ s'obtient à partir de celle de $T [d : f]$ . Nombre d'additions ?
Mesurer les deux programmes pour $n = 500$ , $1000$ , $2000$ et comparer au programme en $Θ (n)$ du chapitre 11.

Corrigé


static int cubique(int[] T) { int n = T.length, best = 0;  // sous-tableau vide : 0
    for (int d = 0; d < n; d++)
        for (int f = d + 1; f < n + 1; f++) {
            int s = 0;
            for (int i = d; i < f; i++) s = s + T[i];      // s = somme de T[d:f]
            if (s > best) best = s;
        }
    return best;
}

Le nombre d'additions est $\sum_{d} \sum_{f > d} (f - d) = n (n + 1) (n + 2) /6 \in Θ (n^{3})$ .

On conserve la somme courante quand $f$ augmente :


static int quadratique(int[] T) { int n = T.length, best = 0;
    for (int d = 0; d < n; d++) {
        int s = 0;                          // s = somme de T[d:d]
        for (int f = d + 1; f < n + 1; f++) {
            s = s + T[f - 1];               // s = somme de T[d:f]
            if (s > best) best = s;
        }
    }
    return best;
}

$n (n + 1) /2$ additions : $Θ (n^{2})$ .

Sur le tableau $U$ du chapitre 11 ( $n = 9$ ), les deux programmes trouvent $6$ , avec $165$ et $45$ additions. Sur des tableaux aléatoires (programme SommeMaxNaive.java) :


n =  500 : cubique 1739 en 8 ms (20958500 add.), quadratique 1739 en 1 ms (125250 add.)
n = 1000 : cubique 1263 en 48 ms (167167000 add.), quadratique 1263 en 0 ms (500500 add.)
n = 2000 : cubique 3722 en 432 ms (1335334000 add.), quadratique 3722 en 0 ms (2001000 add.)

Quand $n$ double, les additions du programme cubique sont multipliées par $8$ , celles du programme quadratique par $4$ . Le programme du chapitre 11 fait $n$ tours de boucle : $2000$ tours pour $n = 2000$ . (Les temps mesurés dépendent de la machine.)