Un algorithme O (n) peut-il jamais dépasser O (n ^ 2) en termes de temps de calcul?

Question

Supposons que je dispose de deux algorithmes:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

C'est naturellement O(n^2). Supposons que j'ai aussi:

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

C'est - O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

Il semble que même si mon deuxième algorithme est - O(n), il faudra plus de temps. Quelqu'un peut-il développer? Je up parce que je vois souvent des algorithmes où ils vont, par exemple, à effectuer un tri étape première ou quelque chose comme ça, et lors de la détermination totale de la complexité, c'est juste l'élément le plus complexe que les limites de l'algorithme.

Answer 1

En fait big-O est seulement une limite supérieure, ce qui signifie que vous pouvez dire un O(1) algorithme (ou vraiment tout algorithme prenant O(n ou moins de temps) prend ² . À cette fin, nous allons passer en grande-Theta (Θ) la notation, qui est juste serré lié. Voir les définitions officielles pour plus d'informations.

Si vous ne connaissez sur le big-O, il est probable que vous avez (à tort) été enseigné que le big-O est un serré lié. Si oui, vous pouvez probablement juste de supposer big-Theta signifie ce que vous avez appris big-O moyens.

Je vais, pour le reste de cette réponse, supposons que vous m'avez demandé (ou signifié) grand-Thêta, pas grand-O. Si ce n'est, comme déjà mentionné, si parler de big-O, qui serait plutôt un "anything goes" situation - ) on peut être plus rapide, O(n on peut être plus rapide ou ils peuvent prendre la même quantité de temps (asymptotiquement) - on ne peut généralement pas faire en particulier des conclusions significatives quant à la comparaison de la grande-O des algorithmes, on peut seulement dire que, étant donné un big-O d'un algorithme, que cet algorithme ne pourra pas prendre plus que ce laps de temps (asymptotiquement).

---

Asymptotique de la complexité (qui est ce que les deux grands-S et grand-Theta représenter) ignore complètement la constante de facteurs en jeu - il est uniquement destiné à donner une indication de combien de temps de course sera la variation de la taille de l'entrée devient plus grand.

Il est donc certainement possible qu'un ² algorithme peut prendre plus d'une ) un pour certains O(n) - dont O(n ce qui va se passer pour va vraiment dépendre sur les algorithmes de votre exemple, ce sera le cas pour l' ², en ignorant la possibilité d'optimisations de différences entre les deux.

Pour les deux algorithmes prenant ) et Θ(n) du temps respectivement, ce que vous êtes susceptible de voir, c'est que soit:

• L' Θ(n algorithme est plus lente lors de l' ² est petit, l' ) on devient plus lent qu' n augmente
  (ce qui arrive si l' n on est plus complexe, c'est à dire a le plus de facteurs constants), ou
• L' n < 100 on est toujours plus lent.

Bien qu'il est certainement possible que l' Θ(n) algorithme peut être plus lent, puis l' Θ(n un, puis de l' ² un de nouveau, et ainsi de suite en ) augmente, jusqu' Θ(n) devient très grande, à partir de laquelle, à partir de l' n on sera toujours plus lent, bien qu'il est fortement improbable.

---

Pour le mettre à un peu plus de termes mathématiques:

Disons que l' Θ(n algorithme prend ² opérations de quelque ).

Et l' n algorithme prend Θ(n) opérations de quelque Θ(n.

Ceci est en ligne avec la définition officielle, puisque nous pouvons supposer que cela est valable pour ² supérieure à 0 (c'est à dire pour tous les )) et que les deux fonctions entre lesquels le temps est le même.

En ligne avec votre exemple, si vous dites Θ(n) et Θ(n, puis l' ² algorithme serait plus lente jusqu' ), à quel point l' Θ(n) algorithme devenir plus lent.

_{(avec l'aimable autorisation de WolframAlpha)}.

Answer 2

Oui, un algorithme O(n) peut dépasser un O(n²) algorithme en termes de temps d'exécution. Ce qui se passe quand le facteur constant (que nous omettons dans la notation grand O) est grande. Par exemple, dans le code ci-dessus, l'algorithme O(n) aura un grand facteur constant. Ainsi, il sera moins bon qu'un algorithme qui s'exécute en O(n²) pour n < 10.

Ici, n=100 est le cross-over point. Ainsi, lorsqu'une tâche peut être effectuée dans les deux O(n) et O(n²) et le facteur constant de l'algorithme linéaire est plus que celui d'un algorithme quadratique, alors nous avons tendance à préférer l'algorithme le pire temps d'exécution. Par exemple, lors du tri d'un tableau, nous allons passer à l'insertion de tri pour les petits tableaux, même lors de la fusion de tri ou tri rapide exécuter asymptotiquement plus rapide. C'est parce que le tri par insertion a un plus petit facteur constant de fusion/tri rapide et courir plus vite.

Answer 3

Gros O(n) ne sont pas destinés à comparer la vitesse relative des différents algorithmes. Ils sont destinés à mesurer à quelle vitesse le temps d'exécution augmentent lorsque la taille de l'entrée d'augmenter. Par exemple,

• O(n) signifie que si n multiplié par 1000, alors le temps d'exécution est à peu près multiplié par 1000.
• O(n^2) signifie que si n est multiplié par 1000, le fonctionnement est à peu près multiplié par 1000000.

Ainsi, lorsque n est assez grand, tout O(n) algorithme de battre un O(n^2) de l'algorithme. Cela ne signifie pas que quelque chose de fixe, n.

Answer 4

Longue histoire courte, oui, ça peut. La définition de O est basée sur le fait que O(f(x)) < O(g(x)) implique que g(x) prendra définitivement plus de temps à fonctionner que f(x) étant donné un grand Assez x .

Par exemple, il est connu que pour les petites valeurs, le tri par fusion est surperformé par le tri par insertion (si je me souviens bien, cela devrait être vrai pour n inférieur à 31 )

Answer 5

Oui. Le O () signifie seulement la complexité asymptotique. L'algorithme linéaire peut être plus lent que le quadratique, s'il a la même constante de ralentissement linéaire suffisamment grande (par exemple, si le noyau de la boucle est dix fois plus long, il sera plus lent que sa version quadratique).

La notation O () - n’est qu’une extrapolation, bien que très bonne.