Complexité algorithme [Résolu/Fermé]

Signaler
Messages postés
6
Date d'inscription
mercredi 14 août 2013
Statut
Membre
Dernière intervention
22 juin 2014
-
Messages postés
6
Date d'inscription
mercredi 14 août 2013
Statut
Membre
Dernière intervention
22 juin 2014
-
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.

1 réponse

Messages postés
1259
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
384
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";
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 61668 internautes nous ont dit merci ce mois-ci

Messages postés
15932
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 juillet 2020
2 629
"O(n) * O(n) = O(n²)"... je ne suis pas convaincu.

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²)
Messages postés
1259
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
384
Bien vu!
Il faudrait que je ressorte mes livres d'université!
Messages postés
6
Date d'inscription
mercredi 14 août 2013
Statut
Membre
Dernière intervention
22 juin 2014

Ok, merci beaucoup à vous deux !