Quelle est la différence entre & # 920; (n) et O (n)?

Question

Parfois, je vois & # 920; (n) avec l'étrange & # 920; symbole avec quelque chose au milieu de celui-ci, et parfois juste O (n). Est-ce juste une paresse de frappe parce que personne ne sait comment taper ce symbole, ou est-ce que ça veut dire quelque chose de différent?

Answer 1

Explication brève:

  

Si un algorithme est de & # 920; (g (n)), cela signifie que le temps d'exécution de l'algorithme en tant que n (taille d'entrée) devient plus grand est proportionnel à g (n).

     

Si un algorithme est de O (g (n)), cela signifie que le temps d'exécution de l'algorithme lorsque n augmente est au plus proportionnel à g (n).

Normalement, même lorsque les gens parlent de O (g (n)), ils signifient en fait & # 920; (g (n)), mais techniquement, il y a une différence.

Plus techniquement:

O (n) représente la limite supérieure. & # 920; (n) signifie que l’union est étroite. & # 937; (n) représente la limite inférieure.

  

    

f (x) = & # 920; (g (x)) si et seulement f (x) =     O (g (x)) et f (x) = & # 937; (g (x))

  

En gros, quand on dit qu'un algorithme est de O (n), c'est aussi O (n ² ), O (n ^1000000 ), O (2 ⁿ ), ... mais un algorithme & # 920; (n) n'est pas & # 920; (n ² ).

En fait, puisque f (n) = & # 920; (g (n)), des moyennes pour des valeurs suffisamment grandes de n, f (n) peuvent être liées dans c ₁ g (n ) et c ₂ g (n) pour certaines valeurs de c ₁ et c ₂ , c'est-à-dire que le taux de croissance de f est asymptotiquement égal à g : g peut être une limite inférieure et et une limite supérieure de f. Cela implique directement que f peut être une limite inférieure et une limite supérieure de g également. Par conséquent,

  

f (x) = & # 920; (g (x)) si et seulement si g (x) = & # 920; (f (x))

De même, pour afficher f (n) = & # 920; (g (n)), il suffit de montrer que g est une limite supérieure de f (c.-à-d. f (n) = O (g (n))) et f est une borne inférieure de g (c.-à-d. f (n) = & # 937; (g (n)), qui est exactement la même chose que g (n) = O (f (n))). De manière concise,

  

f (x) = & # 920; (g (x)) si et seulement f (x) = O (g (x)) et g (x) = O (f (x))

Il existe également des notations peu-oh et peu-oméga ( & # 969; ) représentant les limites supérieures et inférieures lâches d'une fonction.

Pour résumer:

  

f (x) = O (g (x)) (gros-oh) signifie que   le taux de croissance de f (x) est   asymptotiquement inférieur ou égal   à le taux de croissance de g (x) .

     

f (x) = & # 937; (g (x)) (big-oméga) signifie   que le taux de croissance de f (x) est   asymptotiquement supérieur à ou   égal à le taux de croissance de g (x)

     

f (x) = o (g (x)) (peu-oh) signifie que   le taux de croissance de f (x) est   asymptotiquement inférieur à le   taux de croissance de g (x) .

     

f (x) = & # 969; (g (x)) (petit-oméga) signifie   que le taux de croissance de f (x) est   asymptotiquement supérieur à le   taux de croissance de g (x)

     

f (x) = & # 920; (g (x)) (thêta) signifie que   le taux de croissance de f (x) est   asymptotiquement égal à le   taux de croissance de g (x)

Pour une discussion plus détaillée, vous pouvez lire la définition sur Wikipedia ou consulter un manuel classique. comme Introduction aux algorithmes de Cormen et al.

Answer 2

Il existe un moyen simple (une astuce, je suppose) de se rappeler quelle notation signifie quoi.

Toutes les notations Big-O peuvent être considérées comme ayant une barre.

Lorsque vous regardez un & # 937 ;, la barre est en bas, il s'agit donc d'une limite inférieure (asymptotique).

Lorsque vous regardez un & # 920 ;, la barre est évidemment au milieu. C'est donc un lien étroit (asymptotique).

Lorsque vous écrivez à la main O, vous terminez généralement en haut et dessinez un gribouillis. Donc, O (n) est la limite supérieure de la fonction. Pour être juste, celle-ci ne fonctionne pas avec la plupart des polices, mais c'est la justification originale des noms.

Answer 3

on est Big "O"

on est Big Theta

http://fr.wikipedia.org/wiki/Big_O_notation

Big O signifie que votre algorithme ne s'exécutera pas plus rapidement que dans une expression donnée (n ^ 2)

Big Omega signifie que votre algorithme s'exécutera en pas moins que dans l'expression donnée (n ^ 2)

Lorsque les deux conditions sont vraies pour la même expression, vous pouvez utiliser la grande notation thêta ....

Answer 4

Plutôt que de fournir une définition théorique, qui est déjà magnifiquement résumée ici, je vais donner un exemple simple:

Supposons que le temps d'exécution de f (i) est O (1) . Vous trouverez ci-dessous un fragment de code dont le runtime asymptotique est & # 920; (n) . Il toujours appelle la fonction f (...) n . La limite inférieure et supérieure est égale à n.

for(int i=0; i<n; i++){
    f(i);
}

Le deuxième fragment de code ci-dessous a le temps d'exécution asymptotique de O (n) . Elle appelle la fonction f (...) au plus n . La limite supérieure est n, mais la limite inférieure pourrait être & # 937; (1) ou & # 937; (log (n)) , en fonction de ce qui se passe à l'intérieur f2 (i) .

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Answer 5

Theta est un moyen abrégé de faire référence à une situtation spéciale où le grand O et Omega sont les mêmes.

Ainsi, si on prétend Theta est l'expression q , ils prétendent aussi nécessairement que Big O est l'expression q et Omega est l'expression q .

Analogie approximative:

Si: Theta affirme que "cet animal a 5 pattes". alors il s'ensuit que: Big O est vrai ("Cet animal a moins de ou égal à 5 ??pattes.") et Omega est vrai ("Cet animal a plus de ou égal à 5 ??pattes.")

Ce n'est qu'une analogie approximative, car les expressions ne sont pas nécessairement des nombres spécifiques, mais des fonctions d'ordre variable, telles que log (n), n, n ^ 2, (etc.).

Answer 6

Un diagramme pourrait faciliter les réponses précédentes. à comprendre:

& # 920; -Notation - Même commande | Notation O - Limite supérieure

En anglais,

À gauche, notez qu'il existe une limite supérieure et une limite inférieure du même ordre de grandeur (c.-à-d. g (n) ). Ignorer les constantes, et si les bornes supérieure et inférieure ont le même ordre de grandeur, on peut valablement dire f (n) = & # 920; (g (n)) ou f (n) est en grand thêta de g (n) .

En commençant par la droite, l’exemple le plus simple, il est dit que la limite supérieure g (n) est simplement l’ordre de grandeur et ignore la constante c (tout comme toute la notation big O le fait).

Answer 7

f (n) appartient à O (n) s'il existe un positif k en tant que f (n) < = k * n

f (n) appartient à & # 920; (n) s'il existe un positif k1 , k2 comme k1 * n < = f (n) < = k2 * n

article de Wikipedia sur la notation Big O

Answer 8

  

Conclusion: nous considérons le gros O, le grand & # 952; et gros & # 937; comme la même chose.

     

Pourquoi? Je vais dire la raison ci-dessous:

     

Tout d'abord, je vais clarifier une affirmation erronée. Certaines personnes pensent que nous nous soucions simplement de la pire complexité temporelle. Nous utilisons donc toujours un grand O au lieu d'un grand & # 952 ;. Je dirai que cet homme fait des conneries. Les bornes supérieure et inférieure sont utilisées pour décrire une fonction et non pour décrire la complexité temporelle. La fonction de pire temps a ses limites supérieure et inférieure; la meilleure fonction temporelle a aussi ses limites supérieure et inférieure.

     

Afin d’expliquer clairement la relation entre le grand O et le grand, j’expliquerai la relation entre le grand O et le petit o en premier. De la définition, nous pouvons facilement savoir que petit o est un sous-ensemble du grand O. Par exemple, & # 65306;

T (n) = n ^ 2 + n, on peut dire T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Mais pour petit o, T (n) = o (n ^ 2) ne correspond pas à la définition de petit o. Donc, juste T (n) = o (n ^ 3), T (n) = o (n ^ 4) sont corrects pour petit o. Le redondant T (n) = O (n ^ 2) est quoi? C'est grand & # 952;!

  

En général, on dit que grand est O (n ^ 2), difficilement dire que T (n) = O (n ^ 3), T (n) = O (n ^ 4). Pourquoi? Parce que nous considérons le grand O comme un grand & # 952; inconsciemment.

     

De même, nous considérons également les gros & # 937; aussi gros & # 952; inconsciemment.

     

En un mot, gros O, grand & # 952; et gros & # 937; ne sont pas la même chose des définitions, mais ce sont la même chose dans notre bouche et notre cerveau.

Answer 9

Utilisation des limites

Considérons f (n) > 0 et g (n) > 0 pour tout n . Vous pouvez en tenir compte, car l'algorithme réel le plus rapide comporte au moins une opération et termine son exécution après le début. Cela simplifiera le calcul, car nous pouvons utiliser la valeur ( f (n) ) au lieu de la valeur absolue ( | f (n) | ).

1. f (n) = O (g (n))

   Général:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞   g(n)
   

   Pour g (n) = n :

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞    n
   

   Exemples:

       Expression               Value of the limit
   ------------------------------------------------
   n        = O(n)                      1
   1/2*n    = O(n)                     1/2
   2*n      = O(n)                      2
   n+log(n) = O(n)                      1
   n        = O(n*log(n))               0
   n        = O(n²)                     0
   n        = O(nⁿ)                     0
   

   Contre-exemples:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ O(log(n))                 ∞
   1/2*n    ≠ O(sqrt(n))                ∞
   2*n      ≠ O(1)                      ∞
   n+log(n) ≠ O(log(n))                 ∞
   

2. f (n) = & # 920; (g (n))

   Général:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞   g(n)
   

   Pour g (n) = n :

             f(n)     
   0 < lim ──────── < ∞
       n➜∞    n
   

   Exemples:

       Expression               Value of the limit
   ------------------------------------------------
   n        = Θ(n)                      1
   1/2*n    = Θ(n)                     1/2
   2*n      = Θ(n)                      2
   n+log(n) = Θ(n)                      1
   

   Contre-exemples:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ Θ(log(n))                 ∞
   1/2*n    ≠ Θ(sqrt(n))                ∞
   2*n      ≠ Θ(1)                      ∞
   n+log(n) ≠ Θ(log(n))                 ∞
   n        ≠ Θ(n*log(n))               0
   n        ≠ Θ(n²)                     0
   n        ≠ Θ(nⁿ)                     0