Code:
1
2
3
4
5
6
7
8
9
|
seq1:
i=1
while(i<n) do
{
i=2*i;
op;
}
MaSol:T(n)=O(n) |
Je ne pense pas que Seq1 soit O(n),pour voir ça il suffit de le dérouler avec un exemple.
Ici j’ai pris le cas particulier ou n=8
i = 1 = 2^0 -------- 1 exécution de « op »
i = 2 = 2^1 -------- 1 exécution de « op »
i = 4 = 2^2 -------- 1 exécution de « op »
i = 8 = 2^3 -------- Fin de la condition de la boucle.
Pour n=8,l’opération « op » s’est exécutée 3 fois,à travers l’exemple on peut déduire que d’une manière générale l’opération « op » s’exécute « k » fois tel que 2^(k-1)<n<=2^k
Dans le meilleurs des cas on a n=2^k donc k=
Log2 n
Donc T(n) =
Log2 n.
Code:
1
2
3
4
5
6
7
8
9
10
|
seq2:
for i=1 to n do
j=1
while(j<n) do
j=2*j;
op;
end while
end for
MaSol: T(n)=O(n.log(n)) |
Ici Seq1 est exécuté n fois donc ça m'a l'air correcte. T(n) = O(n
Log2 n).
