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²), yO(n) - no en
O(lg n),o(lg n), oo(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:
(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 (norte⁄loglogloglogN). ¡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. 🙂