Complexité algorithme Résolu/Fermé

Question

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.
Configuration: Windows 7 / Chrome 29.0.1547.57

Doctor C · Answer

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";

Complexité algorithme

1 réponse

Discussions similaires