Complexité algorithme
Résolu
azerty27
Messages postés
6
Date d'inscription
Statut
Membre
Dernière intervention
-
azerty27 Messages postés 6 Date d'inscription Statut Membre Dernière intervention -
azerty27 Messages postés 6 Date d'inscription Statut Membre Dernière intervention -
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.
A voir également:
- Complexité algorithme
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
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";
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";
Quand i=1 on fait 1 boucle j, quand i=2 on fait 2 boucles j, , quand i=3 on fait 3 boucles j, etc.
Du coup on fait 1+2+3+...+n boucles j au total. Soit n(n+1)/2 opérations élémentaires x += 3
La complexité est donc de O(n²/2+n/2+1) = O(n²)
Il faudrait que je ressorte mes livres d'université!