Complexité des algos
Résolu
cc
-
cc -
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:
Merci d'avance!
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
Bonjour,
Ton algorithme n'est ni linéaire en
Démonstration :
Soit
Partie 1 :
À l'étape 1 on a
à l'étape k on a
Partie 2 :
Ici, on simplifie avec le résultat de la première partie :
Donc au final, on va faire n*k étapes.
Partie 3 :
Rappel : on est dans le cas où
On va donc faire exactement
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^kavec
kun 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<ndonc 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).
Pour toi, quoi d'autre représente la complexité d'un algorithme ?
Merci pour votre aide!!
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.