Accélération de Knuth — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 9)

Accélération de Knuth

Arbres binaires de recherche de coût minimum · niveau 3 (difficile)

Énoncé

Knuth a montré qu'on peut chercher la racine $k$ de l'arbre optimal sur $[i : j]$ entre les racines des arbres optimaux sur $[i : j - 1]$ et sur $[i + 1 : j]$ : $ar g m (i, j - 1) \leq ar g m (i, j) \leq ar g m (i + 1, j)$ .

Programmer la variante de calculerM dans laquelle, pour $t \geq 2$ , la boucle sur $k$ parcourt $[M [j - 1] [i] : M [j] [i + 1] + 1]$ (rappel : $M [j] [i] = ar g m (i, j)$ ).
Vérifier sur des fréquences aléatoires qu'elle donne les mêmes coûts que la version du cours, et mesurer les temps de calcul pour $n = 200, 400, 800$ .
Montrer que, pour une taille $t$ fixée, la somme des longueurs des intervalles de recherche est au plus $2 n$ . En déduire la complexité.

Corrigé

Les intervalles de taille $1$ sont traités à part (la racine est l'unique valeur), puis la boucle sur $k$ est restreinte :


static int[][] calculerMknuth(int[] F) { int n = F.length;
    int[] P = new int[n + 1];
    for (int x = 0; x < n; x++) P[x + 1] = P[x] + F[x];
    int[][] M = new int[n + 1][n + 1];
    for (int i = 0; i < n; i++) { M[i][i + 1] = F[i]; M[i + 1][i] = i; }   // t = 1
    for (int t = 2; t < n + 1; t++)
        for (int i = 0; i < n - t + 1; i++) { int j = i + t;
            M[i][j] = Integer.MAX_VALUE;
            for (int k = M[j - 1][i]; k < M[j][i + 1] + 1; k++) {  // a(i,j-1) <= k <= a(i+1,j)
                int mikj = M[i][k] + M[k + 1][j];
                if (mikj < M[i][j]) { M[i][j] = mikj; M[j][i] = k; }
            }
            M[i][j] += P[j] - P[i];
        }
    return M;
}

Sur des fréquences aléatoires dans $[1 : 101]$ (les temps dépendent de la machine) :


n=200 : m = 63959 / 63959, Θ(n³) 5,5 ms, Knuth 1,8 ms
n=400 : m = 147539 / 147539, Θ(n³) 19,6 ms, Knuth 1,5 ms
n=800 : m = 340726 / 340726, Θ(n³) 91,4 ms, Knuth 4,0 ms

Les coûts sont identiques. Quand $n$ double, la version du cours est environ $4$ à $5$ fois plus lente (on attendrait $8$ pour de grands $n$ ), la version de Knuth environ $2$ à $3$ fois.

Pour $t$ fixé, l'intervalle $(i, i + t)$ parcourt $a (i, i + t - 1) \leq k \leq a (i + 1, i + t)$ , de longueur $a (i + 1, i + t) - a (i, i + t - 1) + 1$ . En sommant sur $i$ , les termes se télescopent : la somme vaut $a (n - t + 1, n) - a (0, t - 1) + (n - t + 1) \leq 2 n$ . Chaque taille coûte donc $O (n)$ , et les $n$ tailles $O (n^{2})$ : la complexité devient $Θ (n^{2})$ .