Chapitre 4 Diviser pour régner

Question 1

Dans la cas typique d’un algorithme “Diviser pour régner” le temps d’exécution est donnée par

Answer 1

T(n) = r T(n/b) + f(n)

r: Le nombre de sous instances
n/b : La taille de chaque sous instance
Généralement b = r = 2

Question 2

Le gabarit général d’un algorithme “Diviser pour régner”

Answer 2

ALGORITHME DiviserPourRégner(x)
if |x| < seuil return adhoc(x)
diviser x en plus petites instances x1, x2, …, xr
for i ← 1 to r do yi ← DiviserPourRégner(xi)
recombiner les yi pour obtenir la solution y de x
return y

Question 3

Théorème général

Answer 3

Si T(n) obéit à la récurrence T(n) = r T(n/b) + f(n) pour n = bk (avec
k = 1, 2,…), si r > 0, si b > 1 et si f(n) ∈ Θ(nd) avec d ≥ 0, alors:

T(n) ∈ Θ(n^d) si r < b^d
T(n) ∈ Θ(n^d log n) si r = b^d
T(n) ∈ Θ(n^log_b(r)) si r > b^d