TD2EEA .pdf

Exercice 1
Donnés : T[1....n]
1|
2|

f o r i ∈ [ 1 . . . n−1]
k ←− i

(C)

3|

f o r j ∈ [ i +1 . . . n ]

4|
5|

i f T[ j ] < T[ k ]
k←− j

6|

(C’ )
(C’ ’ )

T[ i ↔ k ]

On à utiliser jusqu’a aujourd’hui toute les regles du cours a part celle de la recursion pour calculer la compléxité
(Voir Analysis of Algorithms : Running time dans le cours)
W(1) est une boucle , même si c’est un for il s’agit d’une boucle tout comme while , on se refere donc à la regle
№3 du cour
P#.of.iterations
(W(while (C) S = i
(W (C) + W (S))

W (P r) =PW (1)
W (1) = n−1
i=1 (W (C) + W (2) + W (3) + W (6))
W (C) = 0 car on fait 0 comparaison entre les elements 6= comparaison entre indices
W (2) = 0 comparaison
W (6) = 0 comparaison
W (C 0 ) =P0
W (3) = nj=i+1 [W (C 0 ) + W (4)]
W (4) = W(C”) + W(5) = 1
W (C 00 ) = 1 car on fait une seule comparaison T[j]<T[k]
W (5) = P
0
Pn
W (1) = n−1
j=i+1 1
i=1 ·
On
Pn Calcule de
Pnla somme
Pila plus imbriquée vers l’exterieur
j=i+1 1 =
j=1 1 −
j=1 1 = n − i
Donc :
Pn−1
Pn−1
Pn−1
W(1) = i=1 (n − i) = i=1 n − i=1 i = n(n − 1) − n(n−1)
2
= n(n−1)
⇒ O(n2 )
2
(en comptant la comparaison en temps constant)
ATTENTION : Si on ne considère pas les affectation comme prenant un temps constant on à que
T[i ↔ k] necessite 3 affections , affectation utilisé avec des variable tampon pour faire la permutation.
Pn−1
Notes pour le calcul : i=1 n = n(n − 1)
Pn−1
n(n−1)
i=1 =
2

1

Pour chercher un element dans un tableau l’algo minimal :

T[ i ]
i ←− 1
w h i l e i ≤ n et T [ i ] 6= x
i ++
return ( i ≤ n)

−→ Complexite en O( n )
−→ Algo MASTER

i ←− 1 , T [ n+1] ←− x
w h i l e T [ i ] 6= x
i++
return ( i ≤ n)

−→ Algo Super MASTER

Exercice 2

L ’ a l g o de c e t exemple c a l c u l l e pgcd
x
y
1|

←− q u e l c o n q u e dans N
←− q u e l c o n q u e dans N
w h i l e ( x != y )

2|

−→ C

if x > y

−→ C’

3|

x ←− x − y

4|

e l s e y ←− y − x

5|

return x

W (P r) =PW (1) + W (2)
W (1) = x−1
i=1 [W (C) + W (2)]
W (C) = O(n)
W (2) = W (C 0 ) + max(W (3), W (4))
W (C 0 ) = O(n)
W (3) = O(n)
W (4) = O(n)
Donc

Px−1
i=1

[W (C) + W (2)] =

Px−1
i=1

O(n) = O(x ∗ n)
n = log x ⇒ 2n = x

La compléxité au final est en O(2n n) temps exponentiel

2

Le p i r e c a s : quand y

Exos hors TD en SuperUltraMegaMasterDeLaMort

1|

w h i l e ( y != 0 )

2|
3|
4|

r ←− x
x ←− y
y ←− r mod y

5|

return r

W (P r) = W (1)
Le nombre exact d’opérations en fonction de n est n3
(ici pas de de O(...) car le resultat est exact , on utilise O(n) si on parle de compléxité)
Preuve (hors partiel):
∀ x ∀ y ∃ q ∃ r ( x = y q + r

V

x>y

x mod y

x = d i f f (x

cas 1

:

y >

, y) ∗ y
x
2

⇔ 2 >

V

x
y

r < y)

⇔ ≤ < 2 div (x , y) = 1

x = y + x mod y ⇔ x mod y = x − y <

cas 2

Plogy
i=1

:

y ≤

x
2

x
2

x mod y < y ≤

(W (C) + W (2) + W (3) + W (4)) −→ O(n2 )

n = max( log x log y) =⇒ O(n3 )

3

x
2