Complexité des algos

Bonjour,

Ton algorithme n'est ni linéaire en

O(n)

, ni logarithmique en

O(log n)

, mais il est linéarithmique en

O(n.log n)

.

Démonstration :

Soit

n=2^k

avec

k

un entier.

Partie 1 :

j<--1;
  tant que j<n faire
     j<--j*2

À l'étape 1 on a

j=1=2^0

, à l'étape 2 on a

j=2=2^1

, à l'étape 3 on a

j=4=2^2

,
à l'étape k on a

j=2^(k-1)

et on multiplie à nouveau par 2 pour obtenir

j=2^k=n

, mais on n'a plus

j<n

donc la boucle s'arrête. On a fait

k

étapes.

Partie 2 :

Pour i allant de 1 à n par pas de 1 faire
  j<--1;
  tant que j<n faire
     j<--j*2

Ici, on simplifie avec le résultat de la première partie :

Pour i allant de 1 à n par pas de 1 faire
  k étapes

Donc au final, on va faire n*k étapes.

Partie 3 :

Rappel : on est dans le cas où

n=2^k

, c'est à dire que

k=log2(n)

.

On va donc faire exactement

n*k = n*log2(n)

étapes quand

n=2^k

, ce qui se généralise par un

O(n.log n)

quand n est quelconque (CQFD).