Solution TD1
Exercice N°1
1. T1(n) = 6n3 + 10n2 + 5n + 2 ∈ O(n3)
2. T2(n) = 3 log2 n + 4 ∈ O(log n)
3. T3(n) = 2n + 6n2 + 7n ∈ O(2n) ∈ O(an)
4. T4(n) = 7k + 2 ∈ O(1)
5. T5(n) = 4 log2 n + n ∈ O(n)
6. T6(n) = 2 log10 k + kn2 ∈ O(n2)
Exercice N°2
n = 10: ( 2(10)2 + 210 )10-9 sec ≈ 1.224 *10-6 sec
n = 20: ( 2(20)2 + 220 )10-9 sec ≈ 1.05 *10-3 sec
n = 50: ( 2(50)2 + 250 )10-9 sec ≈ 1.13 *106 sec ≈ 13 jours
n = 100: ( 2(100)2 + 2100 )10-9 sec ≈ 1.27 *1021 sec ≈ 4 *1013 années.
Exercice N°3
1. T1(n) = 9n2 ∈ O(n2 )
T2(n) = 100n + 96 ∈ O(n)
2. A1 : c = 10 et n0 = 1 pour f(n) = O(n2 ) et g(n) = T1(n) = 9n2 car ∀n ≥ 1 : T1(n) ≤ 10n2
A2 : c = 101 et n0 = 100 pour f(n) = O(n) et g(n) = T2(n) = 100n + 96 car ∀n ≥ 100 : T2(n) ≤ 101n
Remarque : Bien sûr, il y a d’autres choix possibles pour c et n0
3. n T1 T2
1 9 196
3 81 396
5 225 596
10 900 1096
14 1764 1496
4
4.
5. Il faut poser : T1(n) = T2(n) <==> 9n2 − 100n − 96 = 0 Equa on quadra que, la seule solu on posi ve est
n = 12. Donc :
0 ≤ n < 12 : L’algorithme A1 est plus efficace
n ≥ 12 : L’algorithme A2 est plus efficace
6. Il faut appliquer la règle des sommes : T1(n) + T2(n) ∈ O(max(n2, n)) = O(n2)
Exercice N°4
Résolvons par substitution :
T(n) = 3T(n-1)
= 3(3T(n-2))
= 32T(n-2)
= 33T(n-3)
...
...
= 3nT(n-n)
= 3nT(0)
= 3n
Cela montre que la complexité de cette fonction est O(3n).
Exercice N°5
1. Le facteur constant c = T(N) / N2, donc T(n) = T(N) (n2 / N2) = n2 / 10000 ms et T(5000) = 2500 ms.
2. Le facteur constant c = T (1000) / f (1000) = 10 / f (1000) millisecondes par élément. Par conséquent, T
(n) = 10 (f (n) / f (1000)) ms et T (100000) = 10 (f (100000) / f (1000)) ms. Si f (n) = n alors T (100000) =
1000 ms. Si f (n) = n3, alors T (100000) = 107 ms.
Exercice N°6
Dans le sens Big-Oh, l'algorithme B est meilleur. Il surpasse l'algorithme A lorsque TB(n) <= TA(n), c'est-à-
dire lorsque 2,5 n2 <= 0,1 n2 log10(n). Cette inégalité se réduit à log10(n) >= 25 ou n >= n0 = 1025. Si n <= 109,
l’algorithme de choix est A.
5
Exercice N°7
int search(int v[], int n, int x) {
int i = 0, found = 0; c1 2
while (i < n && !found) { c2 3n +3 (3 Pour dernier test de sortie)
if (v[i] == x) c3 n
found = 1; c4 0/1
i++; c5 2n
if (!found) c6 1
return -1; c7 0/1
else return i-1; c8 2/0
Le cas le plus défavorable survient lorsque l'élément x n'existe pas dans v ou que v est dans la
dernière case, ce qui signifie que la boucle while s'exécutera 3n + 3 fois (Le 3 est pour les opérations
des 3 tests et +3 ici est parce que le test de la boucle while doit être exécuté une dernière fois pour
savoir qu'il est terminé). Le test dans le if ne sera jamais vrai pour v inexistant et donc = 0 ou 1 si v
existe. Le nombre total d’opérations sera alors
Cas v inexistant : 2 + 3n + 3 + n + 0 + 2n + 1 + 1 = 7 + 6n opérations.
Cas v existant dans la dernière case : 2 + 3n + 3 + n + 1 + 2n + 1 + 2 = 9 + 6n opérations (c’est le pire
par rapport au cas v inexistant).
Le meilleur scénario se produit lorsque l’élément x est trouvé en première position, ce qui signifie
que la boucle while ne fonctionnera qu'une fois. Nous avons donc : 9 + 6x1 = 15 opérations.
Exercice N°8
Dans le sens Big-Oh (Grand O), l’application B de complexité linéaire O (n) est meilleure que
l’application A de complexité O (n log n). Donc, les fonctions de temps associées sont à une
constante prêt, soit TA (n) = cA n log10 n et TB (n) = cB n. Le test pour 104 données nous permet de
dériver les facteurs constants :
cA n log10 n = 100, soit pour n = 104 on a cA 104 log10 104 = 100 => cA = 100/(104 log10 104) = 100/104x 4
= 1/400
cB n = 500, soit pour n = 104 on a cB 104 = 500 on a cB 104 = 500 => cB = 500/104 = 1/20
L’application B commence à surpasser l’application A à partir de la taille de données n0 qui assurent
TA (n0) >= TB (n0), c'est-à-dire quand :
cA n0 log10 n0 >= cB n0, soit (1/400) n0 log10 n0 >= (1/20) n0
Cette inégalité se réduit à
6
log10 n0 >= 400/20, soit log10 n0 >= 20 ==> n0 >= 1020
Ainsi pour le traitement de 109 éléments de données, l’application de choix est A car 109 < 1020