Diferencia entre notación Big-O y Little-O

Respuestas:

443

f ∈ O (g) dice, esencialmente

Para al menos una opción de una constante k > 0, puede encontrar una constante a tal que la desigualdad 0 <= f (x) <= kg (x) se mantenga para todo x> a.

Tenga en cuenta que O (g) es el conjunto de todas las funciones para las que se cumple esta condición.

f ∈ o (g) dice, esencialmente

Para cada elección de una constante k > 0, puede encontrar una constante a tal que la desigualdad 0 <= f (x) <kg (x) se mantenga para todas las x> a.

Una vez más, tenga en cuenta que o (g) es un conjunto.

En Big-O, solo es necesario que encuentre un multiplicador particular k para el cual la desigualdad se mantenga más allá de algún mínimo x .

En Little-o, debe ser que hay un mínimo x después del cual la desigualdad se mantiene sin importar cuán pequeño haga k , siempre que no sea negativo o cero.

Ambos describen límites superiores, aunque algo contraintuitivamente, Little-o es la declaración más fuerte. Existe una brecha mucho mayor entre las tasas de crecimiento de f y g si f ∈ o (g) que si f ∈ O (g).

Una ilustración de la disparidad es esta: f ∈ O (f) es verdadera, pero f ∈ o (f) es falsa. Por lo tanto, Big-O puede leerse como "f ∈ O (g) significa que el crecimiento asintótico de f no es más rápido que el de g", mientras que "f ∈ o (g) significa que el crecimiento asintótico de f es estrictamente más lento que el de g". Es como <=versus <.

Más específicamente, si el valor de g (x) es un múltiplo constante del valor de f (x), entonces f ∈ O (g) es verdadero. Es por eso que puede soltar constantes cuando trabaja con notación big-O.

Sin embargo, para que f ∈ o (g) sea cierto, entonces g debe incluir una mayor potencia de x en su fórmula, por lo que la separación relativa entre f (x) y g (x) en realidad debe aumentar a medida que x aumenta.

Para usar ejemplos puramente matemáticos (en lugar de referirse a algoritmos):

Lo siguiente es cierto para Big-O, pero no sería cierto si usaras little-o:

  • x² ∈ O (x²)
  • x² ∈ O (x² + x)
  • x² ∈ O (200 * x²)

Lo siguiente es cierto para little-o:

  • x² ∈ o (x³)
  • x² ∈ o (x!)
  • ln (x) ∈ o (x)

Tenga en cuenta que si f ∈ o (g), esto implica f ∈ O (g). por ejemplo, x² ∈ o (x³), por lo que también es cierto que x² ∈ O (x³), (nuevamente, piense en O as <=y o as <)

Tyler McHenry
fuente
146
Sí, la diferencia está en si las dos funciones pueden ser asintóticamente iguales. Intuitivamente, me gusta pensar que el significado de O grande "crece no más rápido que" (es decir, crece al mismo ritmo o más lento) y el significado de O pequeño "crece estrictamente más lento que".
Phil
12
¿Copiar esto a wikipedia? Esto es mucho mejor que lo que hay allí.
cloudsurfin el
1
@SA Sí. Ese es un caso más complicado en el que la regla más simple que di sobre "poderes superiores de x" obviamente no es aplicable. Pero si observa las definiciones de límites más rigurosas que figuran en la respuesta de Strilanc a continuación, lo que quiere saber es si lim n-> inf (2 ^ n / 3 ^ n) = 0. Dado que (2 ^ n / 3 ^ n) = (2/3) ^ ny como para cualquier 0 <= x <1, lim n-> inf (x ^ n) = 0, es cierto que 2 ^ n = o (3 ^ n).
Tyler McHenry
1
Tenga cuidado con "En Little-o, debe ser que hay un mínimo x después del cual la desigualdad se mantiene sin importar cuán pequeño haga k, siempre que no sea negativo o cero". No es "para todos los aque hay kque: ...", que es "por cada khay una aque: ..."
GA1
1
"En Little-o, debe ser que hay un mínimo x después del cual la desigualdad se mantiene sin importar cuán pequeño haga k, siempre que no sea negativo o cero". No, esto es incorrecto.
Filippo Costa
196

Big-O es a little-o como ≤es <. Big-O es un límite superior inclusivo, mientras que little-o es un límite superior estricto.

Por ejemplo, la función f(n) = 3nes:

  • en O(n²), o(n²)yO(n)
  • no en O(lg n), o(lg n)oo(n)

Análogamente, el número 1es:

  • ≤ 2` < 2` y≤ 1
  • No ≤ 0, < 0o< 1

Aquí hay una tabla que muestra la idea general:

Mesa grande o

(Nota: la tabla es una buena guía, pero su definición de límite debe ser en términos del límite superior en lugar del límite normal. Por ejemplo, 3 + (n mod 2) oscila entre 3 y 4 para siempre. Está dentro a O(1)pesar de no tener un límite normal, porque todavía tiene a lim sup: 4.)

Recomiendo memorizar cómo la notación Big-O se convierte en comparaciones asintóticas. Las comparaciones son más fáciles de recordar, pero menos flexibles porque no se pueden decir cosas como n O (1) = P.

Craig Gidney
fuente
Tengo una pregunta: ¿cuál es la diferencia entre la línea 3 y 4 (columna de definiciones de límite)? ¿Podría mostrarme un ejemplo en el que 4 contiene (lim> 0), pero no 3?
Hombre enmascarado
3
Oh, lo descubrí. Big Omega es para lim> 0, Big Oh es para lim <infinito, Big Theta es cuando ambas condiciones se cumplen, lo que significa 0 <lim <infinito.
Hombre enmascarado
Para f ∈ Ω (g), ¿no debería el límite en el infinito evaluar a> = 1? De manera similar para f ∈ O (g), 1 = <c <∞?
user2963623
1
@ user2963623 No, porque los valores finitos estrictamente superiores a 0, incluidos los valores entre 0 y 1, corresponden a "la misma complejidad asintótica pero diferentes factores constantes". Si omite valores por debajo de 1, tiene un límite en el espacio de factor constante en lugar de en el espacio de complejidad asintótica.
Craig Gidney
1
@ubadub Usted difunde la operación de exponenciación sobre el conjunto. Es una notación suelta.
Craig Gidney
45

Encuentro que cuando no puedo comprender algo conceptualmente, pensar en por qué uno usaría X es útil para entender X. (Sin decir que no lo has intentado, solo estoy preparando el escenario).

[cosas que sabes] Una forma común de clasificar algoritmos es en tiempo de ejecución, y citando la complejidad de un algoritmo big-Oh, puedes obtener una muy buena estimación de cuál es "mejor", el que tenga la función "más pequeña" en el O! Incluso en el mundo real, O (N) es "mejor" que O (N²), salvo cosas tontas como constantes supermasivas y similares. [/ Cosas que sabes]

Digamos que hay algún algoritmo que se ejecuta en O (N). Bastante bien, ¿eh? Pero digamos que (usted, persona brillante, usted) se le ocurre un algoritmo que se ejecuta en O ( N ⁄ loglogloglogN ). ¡HURRA! ¡Es mas rapido! Pero te sentirías tonto escribiendo eso una y otra vez cuando escribes tu tesis. Entonces, lo escribe una vez y puede decir: "En este documento, he demostrado que el algoritmo X, previamente computable en el tiempo O (N), es de hecho computable en o (n)".

Por lo tanto, todos saben que su algoritmo es más rápido, por cuánto no está claro, pero saben que es más rápido. Teóricamente :)

agorenst
fuente