Sommes préfixes — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Sommes préfixes

Complexité des programmes · niveau 1 (application)

Énoncé

Étant donné un tableau $T [0 : n]$ , on veut le tableau $S [0 : n + 1]$ de terme général $S [k] = \sum_{i \in [0 : k]} T [i]$ (somme du $k$ -préfixe).

Un premier programme calcule chaque $S [k]$ par une boucle sur $[0 : k]$ . Combien d'additions fait-il ? Quelle est sa complexité ?
Écrire un programme en $Θ (n)$ , en remarquant que $S [k + 1] = S [k] + T [k]$ .
À quoi servent ces sommes ? Montrer qu'avec $S$ , la somme de n'importe quel sous-tableau $T [d : f]$ se calcule en temps constant.

Corrigé

Le calcul de $S [k]$ fait $k$ additions, d'où $0 + 1 + \dots + n = n (n + 1) /2$ additions : $Θ (n^{2})$ .
On calcule les $S [k]$ par $k$ croissants, chacun à partir du précédent :


static int[] sommesPrefixes(int[] T) { int n = T.length;
    int[] S = new int[n + 1];             // S[0] = 0 : somme du 0-préfixe
    for (int k = 0; k < n; k++)           // S[0:k+1] est calculé
        S[k + 1] = S[k] + T[k];           // somme de T[0:k+1]
    return S;                             // S[0:n+1] est calculé
}

Exactement $n$ additions : $Θ (n)$ . Sur $T = [3, - 1, 4, 1, - 5, 9]$ :


naif     : [0, 3, 2, 6, 7, 2, 11]  additions = 21
lineaire : [0, 3, 2, 6, 7, 2, 11]  additions = 6
n =  1000 : naif 500500 additions, lineaire 1000 additions
n = 10000 : naif 50005000 additions, lineaire 10000 additions


nom : S
valeurs : 0 3 2 6 7 2 11
fleches : 0->1:+3 1->2:-1 2->3:+4 3->4:+1 4->5:-5 5->6:+9
legende : S[k+1] = S[k] + T[k] : une addition par case

$\sum_{i \in [d : f]} T [i] = S [f] - S [d]$ : une soustraction. Après un précalcul en $Θ (n)$ , chaque somme de sous-tableau coûte un temps constant. C'est une petite programmation dynamique : la récurrence $S [k + 1] = S [k] + T [k]$ évite de recalculer les sommes des préfixes.


nom : T
valeurs : 3 -1 4 1 -5 9
vert : 1..3
zone : 1..3 somme 4
legende : T[1] + T[2] + T[3] = S[4] - S[1] = 7 - 3 = 4