Résoudre des récurrences — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 13)

Résoudre des récurrences

Diviser pour régner · niveau 2

Énoncé

Donner la complexité de chacun des temps de calcul suivants ( $α > 0$ , $n$ puissance de $2$ quand on divise par $2$ ) :

On compare, comme dans le théorème maître, le nombre $a$ d'appels au facteur $b^{2} = 4$ du coût non récursif $α n^{2}$ .

$a = 2 < 4$ : le travail du premier niveau domine. Les niveaux coûtent $α n^{2}$ , $α n^{2} /2$ , $α n^{2} /4$ … : la somme est inférieure à $2 α n^{2}$ , et $T (n) = Θ (n^{2})$ .
$a = 8 > 4$ : les feuilles dominent. Il y a $8^{l o g_{2} n} = n^{3}$ feuilles : $T (n) = Θ (n^{3})$ . Couper les matrices en blocs ne fait rien gagner sur le produit usuel.
$a = 7 > 4$ : $T (n) = Θ (7^{l o g_{2} n}) = Θ (n^{l o g_{2} 7}) \approx Θ (n^{2, 807})$ . Économiser un produit sur huit (Strassen, 1969) fait baisser l'exposant, comme Karatsuba pour les entiers.
Ce n'est pas un partage en moitiés : en déroulant, $T (n) = T (0) + α (1 + 2 + \dots + n) = T (0) + α \frac{n ( n + 1 )}{2}$ , soit $Θ (n^{2})$ . C'est le temps du tri par insertion ou du tri rapide dans le pire cas : diviser en « une valeur » et « le reste » ne sert à rien.