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

Sommes préfixes

Arbres binaires de recherche de coût minimum · niveau 2

Énoncé

Dans calculerM, la somme $S (i, j) = f_{i} + \dots + f_{j - 1}$ est recalculée pour chaque intervalle.

On pose $P [x] = f_{0} + \dots + f_{x - 1}$ pour $0 \leq x < n + 1$ . Montrer que $S (i, j) = P [j] - P [i]$ et calculer $P$ en $Θ (n)$ .
Modifier calculerM pour que chaque $S (i, j)$ soit obtenue en temps constant.
La complexité de calculerM change-t-elle ?

Corrigé

$P [j] - P [i] = (f_{0} + \dots + f_{j - 1}) - (f_{0} + \dots + f_{i - 1}) = f_{i} + \dots + f_{j - 1} = S (i, j)$ . On calcule $P [0] = 0$ puis $P [x + 1] = P [x] + f_{x}$ : $n$ additions.


nom : P
valeurs : 0 2 3 6 10
colorier : 1 3
fleches : 0->1:+2 1->2:+1 2->3:+3 3->4:+4
legende : F = [2, 1, 3, 4] : S(1,3) = P[3] - P[1] = 6 - 2 = 4

Seule la ligne qui ajoute la somme change :


int[] P = new int[n + 1];                          // P[x] = f_0 + ... + f_{x-1}
for (int x = 0; x < n; x++) P[x + 1] = P[x] + F[x];
// ... boucles sur t, i, k inchangées, puis :
M[i][j] += P[j] - P[i];                            // S(i,j) en temps constant

Non : la boucle sur $k$ coûte déjà $Θ (t)$ pour chaque intervalle de taille $t$ , autant que le calcul naïf de $S (i, j)$ . On gagne un facteur constant (environ $2$ ), la complexité reste $Θ (n^{3})$ .