Complexité temporelle de deux boucles for

Question

Je sais donc que la complexité temporelle de :

for(i;i<x;i++){
   for(y;y<x;y++){
      //code
   }
}

est n^2

mais le ferait :

for(i;i<x;i++){
   //code
}
for(y;y<x;y++){
   //code
}

être n+n ?

Answer 1

Étant donné que la notation big-O ne vise pas à comparer la complexité absolue, mais uniquement la complexité relative, O(n+n) est en fait identique à O(n). Chaque fois que vous doublez x, votre code prendra deux fois plus de temps qu'avant, ce qui signifie O(n). Que votre code passe par 2, 4 ou 20 boucles n'a pas d'importance, puisque quel que soit le temps qu'il prend pour 100 éléments, il prendra deux fois plus de temps pour 200 éléments et 100 fois plus de temps pour 10'000 éléments, peu importe le temps passé dans chaque boucle.

C'est pourquoi Big-O ne parle pas de vitesse absolue. Celui qui suppose qu'une fonction O(n^2) f() est toujours plus lente qu'une fonction O(log n) g(), a tort. La notation big-O dit seulement que si vous continuez à augmenter n, il y aura un point où g() dépassera f() en vitesse, cependant, si n reste toujours en dessous de ce point dans la pratique, alors f() peut toujours être plus rapide que g() dans le code du programme réel.

Exemple 1
Supposons que f(x) prenne 5 ms pour un seul élément et que g(x) prenne 100 ms pour un seul élément, mais f(x) est O(n^2), g(x) est O(log2 n). Le graphique temporel ressemblera à ceci :

Note : Jusqu'à 7 éléments, f(x) est plus rapide, même si c'est O(n^2).
Pour 8 éléments ou plus, g(x) est plus rapide.

Exemple 2
Une recherche binaire est O(log n), une table de hachage idéale (sans collisions) est O(1), mais croyez-moi, une table de hachage n'est pas toujours toujours plus rapide qu'une recherche binaire dans la réalité. En utilisant une bonne fonction de hachage, le hachage d'une chaîne peut prendre plus de temps que la recherche binaire entière. D'autre part, l'utilisation d'une mauvaise fonction de hachage crée beaucoup de collisions et plus il y a de collisions, plus la consultation de votre table de hachage ne sera pas vraiment O(1), car la plupart des tables de hachage résolvent les collisions d'une manière qui rendra les consultations soit O(log2 n) soit même O(n).

Answer 2

Ce serait 2n, donc oui, tu as raison.

Cependant, elle est généralement exprimée par O(n), étant donné qu'elle est linéaire plutôt que quadratique.

Cela dépend bien sûr du code qui se trouve dans les boucles, mais je suppose que vous le savez déjà.