Complexité algorithme
Résolu
azerty27
Messages postés
8
Statut
Membre
-
azerty27 Messages postés 8 Statut Membre -
azerty27 Messages postés 8 Statut Membre -
Bonjour,
Voici un algorithme dont je ne comprends pas la complexité :
pour i = 5 a n-5 faire
pour j = i-5 a i+5 faire
x += 3
La complexité semble êre en O(n). La boucle interne a toujours un nombre constant d'opérations (10 etapes) et les variations de longueur sur la boucle externe étant constantes, on les ignore.
Alors que l'algo suivant a une complexité en O(n²) :
pour i = 1 a n faire
pour j = 1 a i faire
x += 3
On n'a donc pas considéré constantes les variations de longueur sur la boucle externe.
Comment expliquer cela ? Quelle est la différence entre ces deux algorithmes au niveau calcul de complexité ?
Merci.
Voici un algorithme dont je ne comprends pas la complexité :
pour i = 5 a n-5 faire
pour j = i-5 a i+5 faire
x += 3
La complexité semble êre en O(n). La boucle interne a toujours un nombre constant d'opérations (10 etapes) et les variations de longueur sur la boucle externe étant constantes, on les ignore.
Alors que l'algo suivant a une complexité en O(n²) :
pour i = 1 a n faire
pour j = 1 a i faire
x += 3
On n'a donc pas considéré constantes les variations de longueur sur la boucle externe.
Comment expliquer cela ? Quelle est la différence entre ces deux algorithmes au niveau calcul de complexité ?
Merci.
1 réponse
-
Bon, mes cours d'analyse d'algo sont un peu loin mais voici ma pensée:
Algo 1:
La boucle externe (i) varie selon le nombre d'éléments à traiter n moins 10. Cette boucle a une complexité de O(n-10) ce qui peut être réduit à O(n).
La boucle interne (j) possède une complexité constante, c'est-à-dire 10.
L'algorithme aurait donc une complexité de O(10n), la constante étant négligeable, on peut simplement retirer le 10 et on obtient: O(n)
Algo 2:
La boucle externe (i) varie selon le nombre d'éléments à traiter n. Cette boucle a une complexité de O(n).
La boucle interne (j) varie proportionnellement à i (qui est directement lié à n), cette boucle possède donc aussi une complexité de O(n).
L'algorithme aura donc une complexité de O(n) * O(n) = O(n²).
Echo "Lima Mike Alfa";
