Complexité des algos [Résolu/Fermé]

Signaler
-
 cc -
Bonjour,

J'ai du mal a calculer la complexité des algos.
Par exemple en cours, on a dit que la complexité est logarithmique pour cet algo alors que pour moi c'est linéaire.
Voici l'algo:

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


Merci d'avance!

1 réponse

Messages postés
15928
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
1 juillet 2020
2 625
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).
Ok!Donc le nombre d'étapes de l'algo représente aussi la complexité?
Messages postés
15928
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
1 juillet 2020
2 625
Bien sûr, c'est même plus ou moins la définition de la complexité...
Pour toi, quoi d'autre représente la complexité d'un algorithme ?
Pour moi c'est la mesure du temps d'éxécution de l'algorithme.
Merci pour votre aide!!
Messages postés
15928
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
1 juillet 2020
2 625
Mais le temps dépends du nombre d'étapes à effectuer...

Le temps d'exécution d'un programme peut changer d'un ordinateur à un autre selon la performance de ceux-ci, par contre le nombre d'étapes de l'algorithme va rester le même, c'est donc le seul calcul fiable susceptible de nous intéresser.