¿Cuál es la diferencia entre & # 920; (n) y O (n)?

Question

A veces veo & # 920; (n) con el extraño & # 920; símbolo con algo en el medio y, a veces, solo O (n). ¿Es solo la pereza de escribir porque nadie sabe cómo escribir este símbolo, o significa algo diferente?

Answer 1

Breve explicación:

  

Si un algoritmo es de & # 920; (g (n)), significa que el tiempo de ejecución del algoritmo a medida que n (tamaño de entrada) aumenta es proporcional a g (n).

     

Si un algoritmo es de O (g (n)), significa que el tiempo de ejecución del algoritmo a medida que n aumenta es como máximo proporcional a g (n).

Normalmente, incluso cuando las personas hablan de O (g (n)) en realidad quieren decir & # 920; (g (n)) pero técnicamente, hay una diferencia.

---

Más técnicamente:

O (n) representa el límite superior. & # 920; (n) significa límite apretado. & # 937; (n) representa el límite inferior.

  

    

f (x) = & # 920; (g (x)) iff f (x) =     O (g (x)) yf (x) = & # 937; (g (x))

  

Básicamente, cuando decimos que un algoritmo es de O (n), también es O (n ² ), O (n ^1000000 ), O (2 ⁿ ), ... pero un algoritmo & # 920; (n) es no & # 920; (n ² ).

De hecho, dado que f (n) = & # 920; (g (n)) significa que para valores suficientemente grandes de n, f (n) puede unirse dentro de c ₁ g (n ) y c ₂ g (n) para algunos valores de c ₁ y c ₂ , es decir, la tasa de crecimiento de f es asintóticamente igual a g : g puede ser un límite inferior y y un límite superior de f. Esto implica directamente que f puede ser un límite inferior y también un límite superior de g. En consecuencia,

  

f (x) = & # 920; (g (x)) iff g (x) = & # 920; (f (x))

Del mismo modo, para mostrar f (n) = & # 920; (g (n)), es suficiente mostrar que g es un límite superior de f (es decir, f (n) = O (g (n))) y f es un límite inferior de g (es decir, f (n) = & # 937; (g (n)) que es exactamente lo mismo que g (n) = O (f (n))). Conciso,

  

f (x) = & # 920; (g (x)) iff f (x) = O (g (x)) y g (x) = O (f (x))

---

También hay anotaciones little-oh y little-omega ( & # 969; ) que representan los límites superiores e inferiores sueltos de una función.

Para resumir:

  

f (x) = O (g (x)) (big-oh) significa que   la tasa de crecimiento de f (x) es   asintóticamente menor o igual    a la tasa de crecimiento de g (x) .

     

f (x) = & # 937; (g (x)) (big-omega) significa   que la tasa de crecimiento de f (x) es   asintóticamente mayor que o   igual a la tasa de crecimiento de g(x)

     

f (x) = o (g (x)) (little-oh) significa que   la tasa de crecimiento de f (x) es   asintóticamente menor que el   tasa de crecimiento de g (x) .

     

f (x) = & # 969; (g (x)) (little-omega) significa   que la tasa de crecimiento de f (x) es   asintóticamente mayor que el   tasa de crecimiento de g(x)

     

f (x) = & # 920; (g (x)) (theta) significa que   la tasa de crecimiento de f (x) es   asintóticamente igual a el   tasa de crecimiento de g(x)

Para una discusión más detallada, puede leer la definición en Wikipedia o consultar un libro de texto clásico como Introducción a los algoritmos de Cormen et al.

Answer 2

Hay una manera simple (un truco, supongo) para recordar qué notación significa qué.

Se puede considerar que todas las anotaciones Big-O tienen una barra.

Al mirar un & # 937 ;, la barra está en la parte inferior, por lo que es un límite inferior (asintótico).

Al mirar un & # 920 ;, la barra está obviamente en el medio. Por lo tanto, es un límite apretado (asintótico).

Al escribir O, generalmente termina en la parte superior y dibuja un garabato. Por lo tanto, O (n) es el límite superior de la función. Para ser justos, este no funciona con la mayoría de las fuentes, pero es la justificación original de los nombres.

Answer 3

uno es grande " O "

uno es Big Theta

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

Big O significa que su algoritmo se ejecutará en no más pasos que en la expresión dada (n ^ 2)

Big Omega significa que su algoritmo se ejecutará en no menos pasos que en la expresión dada (n ^ 2)

Cuando ambas condiciones son verdaderas para la misma expresión, puede usar la notación theta grande ...

Answer 4

En lugar de proporcionar una definición teórica, que ya se resumen maravillosamente aquí, daré un ejemplo simple:

Suponga que el tiempo de ejecución de f (i) es O (1) . A continuación se muestra un fragmento de código cuyo tiempo de ejecución asintótico es & # 920; (n) . siempre llama a la función f (...) n veces. Tanto el límite inferior como el superior es n.

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

El segundo fragmento de código a continuación tiene el tiempo de ejecución asintótico de O (n) . Llama a la función f (...) a lo sumo n veces. El límite superior es n, pero el límite inferior podría ser & # 937; (1) o & # 937; (log (n)) , dependiendo de lo que ocurra dentro f2 (i) .

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

Answer 5

Theta es una forma abreviada de referirse a una situación especial donde la gran O y Omega son lo mismo.

Por lo tanto, si uno reclama Theta es la expresión q , entonces también está necesariamente afirmando que Big O es la expresión q y Omega es la expresión q .

---

Analogía aproximada:

Si: Theta afirma: "Ese animal tiene 5 patas". entonces se sigue que: Big O es cierto (" Ese animal tiene menos o igual a 5 patas. & Quot;) y Omega es cierto (" Ese animal tiene más de o igual a 5 patas. & Quot;)

Es solo una analogía aproximada porque las expresiones no son necesariamente números específicos, sino que funcionan de diferentes órdenes de magnitud, como log (n), n, n ^ 2, (etc.).

Answer 6

Un gráfico podría facilitar las respuestas anteriores entender:

& # 920; -Notación - Mismo orden | Notación O: límite superior

En inglés,

A la izquierda, tenga en cuenta que hay un límite superior y un límite inferior que son del mismo orden de magnitud (es decir, g (n) ). Ignore las constantes, y si el límite superior y el límite inferior tienen el mismo orden de magnitud, se puede decir válidamente f (n) = & # 920; (g (n)) o f (n) está en theta grande de g (n) .

Comenzando con la derecha, el ejemplo más simple, es decir que el límite superior g (n) es simplemente el orden de magnitud e ignora la constante c (tal como toda la notación big O hace).

Answer 7

f (n) pertenece a O (n) si existe k positivo como f (n) < = k * n

f (n) pertenece a & # 920; (n) si existe positivo k1 , k2 como k1*n<=f(n)<=k2*n

Artículo de Wikipedia sobre Big O Notation

Answer 8

  

Conclusión: consideramos grandes O, grandes & # 952; y grande & # 937; como lo mismo

     

¿Por qué? Te diré la razón a continuación:

     

En primer lugar, aclararé una afirmación incorrecta, algunas personas piensan que solo nos importa la peor complejidad de tiempo, por lo que siempre usamos O grande en lugar de grande & # 952 ;. Diré que este hombre es una tontería. Los límites superior e inferior se usan para describir una función, no para describir la complejidad del tiempo. La función de peor tiempo tiene su límite superior e inferior; la mejor función de tiempo también tiene su límite superior e inferior.

     

Para explicar claramente la relación entre O grande y grande & # 952 ;, explicaré primero la relación entre O grande y O pequeño. A partir de la definición, podemos saber fácilmente que una o pequeña es un subconjunto de una gran O. Por ejemplo & # 65306;

T (n) = n ^ 2 + n, podemos decir T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Pero para la pequeña o, T (n) = o (n ^ 2) no cumple con la definición de pequeña o. Entonces, solo T (n) = o (n ^ 3), T (n) = o (n ^ 4) son correctos para o pequeño. El redundante T (n) = O (n ^ 2) es qué? Es grande & # 952 ;!

  

Generalmente, decimos que O grande es O (n ^ 2), difícilmente decir T (n) = O (n ^ 3), T (n) = O (n ^ 4). ¿Por qué? Porque consideramos a O grande como grande & # 952; inconscientemente.

     

Del mismo modo, también consideramos grande & # 937; tan grande & # 952; inconscientemente.

     

En una palabra, O grande, grande & # 952; y grande & # 937; no son lo mismo de las definiciones, pero son lo mismo en nuestra boca y cerebro.

Answer 9

Uso de límites

Consideremos f (n) > 0 y g (n) > 0 para todos los n . Está bien considerar esto, porque el algoritmo real más rápido tiene al menos una operación y completa su ejecución después del inicio. Esto simplificará el cálculo, porque podemos usar el valor ( f (n) ) en lugar del valor absoluto ( | f (n) | ).

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

   General :

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

   Para g (n) = n :

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

   Ejemplos :

       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
   

   Ejemplos de voluntariado :

       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))

   General :

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

   Para g (n) = n :

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

   Ejemplos :

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

   Ejemplos de voluntariado :

       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