Exercice 1
Réponse
Sur des machines réalisant 106 opérations/sec, les temps d’exécution des algorithmes A0..A6 ,
selon leurs complexités et la taille des problèmes(10, 100et 1000), sont donnés dans le tableau
suivant:
Exercice 2
Pour i de 1 a n faire
A[i] := 0 n fois
1 aff +
Pour j de 1 a n faire
A[i] := A[i] + B[i; j] n fois
D[i; j] := 0 2 aff+ 1 add+1 comp + max
Si B[i; j] > 0 alors
Pour k de 1 a n faire
1aff
n fois
D[i; j] := D[i; j] + +1add
B[i; k] *C[k; j] 1Aff+ 1add+1mult
Finpour
Sinon D[i; j] := B[i; j] + C[i; j]
Finpour
Finpour
∑ {1+∑[4+ max(2, ∑3)]} = n{1+n[4+(3n)]} = 3n3 4+n2 +n = O(n3)
Exercice 4
Question
1. Soient les deux fonctions suivantes :
f(n) = n3/2
g(n) = 37n2 + 120n + 17
Montrer que : g(n) ϵ O(f(n))
Preuve : D’après la définition de la notation de complexité grand-O
On dit que T(n) est en O(f(n)) si seulement s’il existe un entier n0 et une
constante c > 0 tel que pour tout n ≥ n0, on a : T (n) ≤ cf(n)
Cherchons n0 tel que n3/2 > (37n2 + 120n + 17) revient à résoudre l’inéquation :
n3/2 – (37n2 + 120n + 17) > 0
la résolution donne n3/2 > (37n2 + 120n + 17) pour tout n ≥ n0= 78, c=1, et n ≥ n0= 10,
c=0.1
2. En utilisant les limites, trouver une relation, en notation asymptotique, entre les
deux fonctions suivantes :
f(n) = 5n3 + 30n2 f(n) est O(n3)
g(n) = 2n + 3n log n g(n) est O(n3 log n)
2 3
f(n) est O(g(n))
3. En utilisant les propriétés de la notation Grand-O, simplifier les expressions
Suivantes :
a. O(f(n) log f(n) + n)
b. O(n2 + f(n) log f(n) + n log n + f(n)2)
c. 3n3 + 2n2f(n)2 + O(n2 + nf(n))
f(n) = O(1) f(n) = O(n) f(n) = O(n2)
O(f(n) log f(n) + n) O(n) O(n log n) O(n2log(n2)
O(n2 + f(n) log f(n) O(n2 ) O(n2 ) O(n4)
+ n log n + f(n)2)
3n3 + 2n2f(n)2 + O(n3 ) O(n4 ) O(n6 )
O(n2 + nf(n))
Exercice 5
Question
1. Proposer une comparaison des deux algorithmes suivants :
A : TA(n) = 100n3
B : TB(n) = n4
Réponse
Pour n =100, TA(n) = TB(n) ; les deux algorithmes ont la même complexité,
Si n < 100 alors TB(n) < TA(n)
Si n > 100 alors TA(n) < TB(n)
On cherche l’algorithme le plus efficace ente A et B, on s’intéresse alors aux grandes valeurs
de n , (TA(n)> TB(n)) on dit que TA(n) est en O(TB(n)),
Exercice 6
Questions
Partant de la propriété suivante : f(n) = O(g(n)) ) O(f(n) + g(n)) = O(g(n)) simplifier les
expressions suivantes :
1— O(n + log n)
2— O(n2 + nlog n)
3— O(nk + nrlog n), k, r entiers > 0 ;
4— O(log n + (log n)2)
5— O( n log n + √𝑛)
6— O(n! + Cn), C entier > 0.
Reponses
1— O(n + log n) = O(n)
2— O(n2 + nlog n) = O(n2)
3— O(nk + nrlog n) = O(max(nk, nrlog n))
= O(max(nk, nrlog n))
4— O(log n + (log n)2)= O((log n)2)
5— O( n log n + √𝑛)= O( n log n )
6— O(n! + Cn)= O(n!)
