TD sur la complexité pratique

Igor Stéphan

20 mars 2000

Références

[JFD95] Y. Bertrand J.-F. Dufourd, D. Bechmann. Spécification algébriques, algorithmique et programmation. InterÉditions, 1995.

Un exemple simple

Calculons la complexié Tproc(n) en nombre de inst de la procedure :

void proc ()
{
int i,j,k;
for (i=1 ; i<=n-1 ; i++)
for (j = i+1 ; j <= n ; j++)
for (k = 1 ; k <= j ; k++)
inst;
}

Tproc(n) = Σ_{i=1}^{n−1}Σ_{j=i+1}^{n}j

or Σ_{j=i+1}^{n}j = Σ_{j=1}^{n}j − Σ_{j=1}^{i}j = \frac{n(n+1)}{2} − \frac{i(i+1)}{2} donc

Tproc(n) = Σ_{i=1}^{n−1}(\frac{n(n+1)}{2} − \frac{i(i+1)}{2})
= Σ_{i=1}^{n−1}(\frac{n(n+1)}{2}) − Σ_{i=1}^{n−1}(\frac{i(i+1)}{2})
= \frac{(n−1)n(n+1)}{2} − \frac{1}{2}Σ_{i=1}^{n−1}i^{2} − \frac{1}{2}Σ_{i=1}^{n−1}i
= \frac{(n−1)n(n+1)}{2} − \frac{1}{2} \frac{(n−1)(2n−1)n}{6} − \frac{1}{2} \frac{(n−1)n}{2}
= \frac{(n−1)n}{2}((n + 1) − \frac{(2n−1)}{6} − \frac{1}{2})
= \frac{(n−1)n}{2}(\frac{6n+6−2n+1−3}{6})
= \frac{(n−1)n}{2}(\frac{4n+4}{6})
= \frac{(n−1)n(n+1)}{3}

Démontrons que Σ_{i=1}^{n}i = \frac{n(n+1)}{2}.

n = 1 Σ_{i=1}^{n}i = 1 = \frac{1(1+1)}{2}.

n ≥ 1 (Σ_{i=1}^{n}i = \frac{n(n+1)}{2}) ⇒^{?} (Σ_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}).

\begin{matrix}Σ_{i=1}^{n+1}i = & (Σ_{i=1}^{n}i) + n + 1 \\ = & \frac{n(n+1)}{2} + n + 1 \\ = & \frac{(n+1)(n+2)}{2} \end{matrix}

Démontrons que Σ_{i=1}^{n}i^{2} = \frac{n(2n+1)(n+1)}{6}.

n = 1 Σ_{i=1}^{n}i^{2} = 1 = \frac{1(2∗1+1)(1+1)}{6}.

n ≥ 1 (Σ_{i=1}^{n}i^{2} = \frac{n(2n+1)(n+1)}{2}) ⇒^{?} (Σ_{i=1}^{n+1}i^{2} = \frac{(n+1)(2n+3)(n+2)}{6}).

\begin{matrix}Σ_{i=1}^{n+1}i = & (Σ_{i=1}^{n}i^{2}) + (n + 1)^{2} \\ = & \frac{n(2n+1)(n+1)}{6} + (n + 1)^{2} \\ = & \frac{(n+1)}{6}(2n^{2} + n + 6n + 6) \\ = & \frac{(n+1)}{6}(2n + 3)(n + 2) \end{matrix}

Un exemple un peu plus complexe

Nous désirons allumer des points sur un écran. Nous supposons connus la primitive allumer telle que allumer(x,y) allume le point de coordonnées (x,y) à l’écran^{1}. Nous décrivons ci-dessous la procédure fleche :

procedure fleche(x, y, h : reel)
begin
   if (y >= h-2)
   then allumer(x,y)
   else begin
      fleche(x-1, y+1, h-1);
      fleche(x, y+1, h);
      fleche(x+1, y+1, h-1)
   end;
end fleche;

Soient F (y) le nombre d’exécutions de la primitive allumer pour l’appel fleche(x,y,h), x, y, h ∈ ℝ; n ∈ ℕ tel que y + n < h ≤ y + (n + 1) et η_{i} = F (y + (n − i)) pour 0 ≤ i ≤ n.

– Dessiner la figure révélée par l’appel fleche(0,0,5). Combien y a-t-il d’exécutions de la primitive allumer? Combien y a-t-il de points effectivement allumés?

1. Nous supposerons que cet écran est infini.

Dans l’exécution de fleche(0,0,5), le nombre d’exécutions de la primitive allumer est 11 pour 8 points allumés.

– Exprimer F (y) en fonction des F (y + k), k ≥ 1.

F (y) = F (y + 1) + 2 ∗ F (y + 2).

– Démontrer par récurrence que ∀n ∈ ℕ, 0 ≤ i ≤ n, η_{i} = \frac{2^{i+1}+(−1)^{i}}{3} . En déduire F (y) en fonction de n. Calculer F (y) pour n = 4.

Soit n ≥ 0

n ≥ i = 0 η_{0} = F (y + n) = 1.

n ≥ i = 1 η_{1} = F (y + (n − 1)) = 1.

n ≥ i > 1 Nous suppons que ∀k < i, η_{k} = \frac{2^{k+1}+(−1)^{k}}{3} et nous démontrons

que η_{i} = \frac{2^{i+1}+(−1)^{i}}{3} .
η_{i} = F (y + (n − i))
= F (y + (n − i) + 1) + 2 ∗ F (y + (n − i) + 2)
= F (y + (n − (i − 1))) + 2 ∗ F (y + (n − (i − 2)))
= η_{i−1} + 2 ∗ η_{i−2}
= \frac{2^{i}+(−1)^{i−1}}{3} + 2 ∗ \frac{2^{i−1}+(−1)^{i−2}}{3}
= \frac{2^{i+1}}{3} + \frac{(−1)^{i−1}}{3} + \frac{2∗(−1)^{i−2}}{3}
= \frac{2^{i+1}}{3} + \frac{(−1)^{i−1}}{3} (1 − 2)
= \frac{2^{i+1}}{3} + \frac{(−1)^{i}}{3}

Donc F (y) = F (y + (n − n)) = η_{n} = \frac{2^{n+1}}{3} + \frac{(−1)^{n}}{3} et F (y) = 11 pour n = 4.

A mauvaise conception, complexité exponentielle

Nous désirons tracer une figure récursive à l’aide d’un crayon dans un repère euclidien. Nous supposons connus les primitives placer(x,y) qui place le crayon au point courant (x,y) et tracer(x,y) qui trace le segment joignant l’ancien point courant au nouveau point courant (x,y). Nous décrivons ci-dessous la

procédure triangles1 :
procedure triangles1(x, y, d, h : reel);
begin
if (y + d < h) then

begin
tracer(x - d, y + d);
triangles1(x - d, y + d, d, h);
tracer(x + d, y + d);
triangles1(x + d, y + d, d, h);
tracer(x, y);
end;
end triangles1;
La séquence placer(x,y); triangles1(x, y, d, h) avec d > 0 trace le

dessin ci-dessous.

Nous notons N_{1}(y) le nombre d’exécutions de la primitive tracer pour l’appel triangles1(x, y, d, h) avec d > 0 Evaluer N_{1}(y) en fonction de N_{1}(y + d).

N_{1}(y) = 2N_{1}(y + d) + 3

Soient n tel que y + nd < h ≤ y + (n + 1)d et η_{i} = N_{1}(y + (n − i)d) pour 0 ≤ i ≤ n. Montrer par récurrence que ∀n(n ∈ ℕ ⇒ ∀i((0 ≤ i ≤ n) ⇒ η_{i} = 3(2^{i} − 1))). En déduire N_{1}(y) en fonction de n. Discuter ce résultat.

Soit n ∈ ℕ, démontrons par récurrence que ∀i((0 ≤ i ≤ n) ⇒ η_{i} = 3(2^{i} −1)).

i = 0 η_{0} = N_{1}(y + nd) = 0 = 3(2^{0} − 1).

0 < i ≤ n Nous supposons que η_{i−1} = 3(2^{i−1} − 1)) et nous démontrons que η_{i} = 3(2^{i} − 1)).

Par définition η_{i} = N_{1}(y + (n − i)d) or N_{1}(y′) = 2N_{1}(y′ + d) + 3 donc η_{i} = 2N_{1}(y + (n − i)d + d) + 3 = 2N_{1}(y + (n − (i − 1))d) + 3 or par hypothèse de récurrence N_{1}(y + (n − (i − 1))d) = η_{i−1} = 3(2^{i−1} − 1) donc η_{i} = 2(3(2^{i−1} − 1)) + 3 = 3(2^{i} − 1).

Donc N_{1}(y) = 3(2^{n} − 1). Les deux appels a triangles tracent deux fois les mêmes triangles intérieurs (et ce récursivement) induisant une complexité exponentielle.

Nous désirons améliorer le traçage du dessin. Nous définissons une procédure bande(x, y, d, h) qui ne trace que les triangles grisés du dessin ci-dessous.

Ecrire en algorithmique impérative la procédure bande. Ecrire une procédure récursive triangle2, en utilisant la procédure bande, qui trace chaque triangle du dessin une seule fois.

procedure bande(x, y, d, h :reel);
begin
if (y + d < h) then
   begin
   tracer(x - d, y + d);
   tracer(x + d, y + d);
   bande(x + d, y + d, d, h);
   tracer(x, y);
   end
end
procedure triangles2(x, y, d, h :reel);
begin
if (y + d < h) then
   begin
   bande(x, y, d, h);
   placer(x - d, y + d);
   triangles2(x - d, y + d, d, h);
   end
end

Nous notons B(y) le nombre d’exécutions de la primitive tracer pour l’appel bande(x, y, d, h) et N_{2}(y) le nombre d’exécutions de la primitive tracer pour l’appel triangles2(x, y, d, h) avec d > 0. Evaluer B(y + (n − i)d) et N_{2}(y + (n − i)d), pour 0 ≤ i ≤ n. En déduire B(y) et N_{2}(y) en fonction de n. Comparer et commenter les résultats de N_{1}(y) et N_{2}(y).

B(y) = B(y + d) + 3 et N_{2}(y) = B(y) + N_{2}(y + d). Montrons que B(y + (n − i)d) = 3i et N_{2}(y + (n − i)d) = \frac{3}{2}(i(i + 1)).

Soit n ∈ ℕ, démontrons par récurrence que ∀i((0 ≤ i ≤ n) ⇒ B(y + (n − i)d) = 3i)

i = 0 B(y + (n − 0)d) = B(y + dn) = 0 = 3 ∗ 0.

0 < i ≤ n Nous supposons que B(y + (n − (i − 1))d) = 3(i − 1) et nous démontrons que B(y + (n − i)d) = 3i.

B(y + (n − i)d) = B(y + (n − i)d + d) + 3 = B(y + (n − (i − 1))d) + 3 or par hypothèse de récurrence B(y + (n − (i − 1))d) = 3(i − 1) donc B(y + (n − i)d) = 3(i − 1) + 3 = 3i.

et que ∀i((0 ≤ i ≤ n) ⇒ N_{2}(y + (n − i)d) = \frac{3}{2}(i(i + 1))

i = 0 N_{2}(y + (n − 0)d) = N_{2}(y + dn) = 0 = \frac{3}{2} ∗ (0 ∗ (0 + 1)).

0 < i ≤ n Nous supposons que N_{2}(y + (n − (i − 1))d) = \frac{3}{2}i(i − 1) et nous démontrons que N_{2}(y + (n − i)d) = \frac{3}{2}i(i + 1).

N_{2}(y + (n − i)d) = B(y + (n − i)d) + N_{2}(y + (n − i)d + d) = B(y + (n − i)d) + N_{2}(y + (n − (i − 1))d) or par hypothèse de récurrence N_{2}(y + (n − (i − 1))d) = \frac{3}{2}(i − 1)i et d’autre part B(y + (n − i)d) = 3i donc N_{2}(y + (n − i)d) = 3i + \frac{3}{2}(i(i − 1)) = \frac{3}{2}(i(i + 1)).

Donc N_{2}(y) = \frac{3}{2}n(n + 1). La complexité de triangles2 n’est que quadratique alors que la complexité

de triangles1 est exponentielle car avec triangles2 les triangles ne sont tracés qu’une seule fois.