Complexité des algos
Résolu/Fermé1 réponse
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
1 nov. 2015 à 16:19
1 nov. 2015 à 16:19
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).
1 nov. 2015 à 20:10
1 nov. 2015 à 20:20
Pour toi, quoi d'autre représente la complexité d'un algorithme ?
1 nov. 2015 à 21:01
Merci pour votre aide!!
1 nov. 2015 à 21:09
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.
1 nov. 2015 à 21:31