Saltar al contenido

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

Solución:

f ∈ O (g) dice, esencialmente

Para al menos uno elección de una constante k > 0, puedes encontrar una constante a tal que la desigualdad 0 <= f (x) <= kg (x) se cumple 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, puedes encontrar una constante a tal que la desigualdad 0 <= f (x) a.

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

En Big-O, solo es necesario que encuentres un multiplicador particular k para el cual la desigualdad se mantiene más allá de un mínimo X.

En Little-o, debe ser que haya un mínimo X después de lo cual la desigualdad se mantiene sin importar cuán pequeña hagas k, siempre que no sea negativo ni cero.

Ambos describen límites superiores, aunque de forma algo contraria a la intuición, 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 la siguiente: 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 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. Esta es la razón por la que puede eliminar constantes cuando trabaja con la notación Big-O.

Sin embargo, para que f ∈ o (g) sea verdadera, entonces g debe incluir una mayor poder de x en su fórmula, por lo que la separación relativa entre f (x) y g (x) debe hacerse más grande a medida que x se hace más grande.

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 usara 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³), (de nuevo, piense en O como <= yo como <)

Big-O es tan pequeño como Es para <. 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) = 3n es:

  • en O(n²), o(n²), y O(n)
  • no en O(lg n), o(lg n), o o(n)

Análogamente, el número 1 es:

  • ≤ 2, < 2, y ≤ 1
  • no ≤ 0, < 0, o < 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 O(1) a pesar de no tener un límite normal, porque todavía tiene un 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 puedes decir cosas como nO (1) = P.

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

[stuff you know]Una forma común de clasificar algoritmos es por tiempo de ejecución, y al citar la complejidad de un algoritmo, puede obtener una estimación bastante buena de cuál es “mejor”, ¡el que tenga la función “más pequeña” en O! Incluso en el mundo real, O (N) es “mejor” que O (N²), salvo cosas tontas como constantes supermasivas y cosas por el estilo.[/stuff you know]

Digamos que hay algún algoritmo que se ejecuta en O (N). Bastante bien, ¿eh? Pero digamos que usted (persona brillante, usted) crea un algoritmo que se ejecuta en O (norteloglogloglogN). ¡HURRA! ¡Es mas rapido! Pero te sentirías tonto escribiendo eso una y otra vez cuando estás escribiendo tu tesis. Así que lo escribe una vez y puede decir: “En este artículo, he probado que el algoritmo X, previamente calculable en el tiempo O (N), es de hecho calculable en o (n)”.

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

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *