algorithm - omega - big o notation java

Diferencia entre Big-O y Little-O Notation (3)

¿Cuál es la diferencia entre la notación Big-O O(n) y la notación Little-O o(n) ?

Big-O es demasiado-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) = 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, mostrando 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á en O(1) a pesar de no tener un límite normal, porque todavía tiene un límite 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 puede decir cosas como n ^{O (1)} = P.

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

[cosas que ya sabes] Una forma común de clasificar los algoritmos es por tiempo de ejecución, y al citar la gran complejidad de un algoritmo, puedes obtener una buena estimación de cuál es "mejor", cualquiera que sea la función "más pequeña" en la O! Incluso en el mundo real, O (N) es "mejor" que O (N²), a menos que haya cosas tontas como constantes super-masivas y similares. [/ Cosas que sabes]

Digamos que hay algún algoritmo que se ejecuta en O (N). Bastante bien, ¿eh? Pero digamos que usted (una persona brillante, usted) tiene un algoritmo que se ejecuta en O ( ^N ⁄ _{loglogloglogN} ). ¡HURRA! ¡Es mas rapido! Pero te sentirías tonto al escribir eso una y otra vez cuando estás escribiendo tu tesis. Así que lo escribes una vez, y puedes decir "En este documento, he probado que el algoritmo X, previamente computable en el tiempo O (N), de hecho es computable en o (n)".

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

f ∈ O (g) dice, esencialmente

Para al menos una elección de una constante k > 0, puede encontrar una constante a tal que la desigualdad 0 <= f (x) <= kg (x) sea válida para todas las 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) sea válida 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 encuentres un multiplicador k particular para el cual la desigualdad se mantenga más allá de un mínimo de 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ña sea k , siempre que no sea negativa o cero.

Ambos describen los límites superiores, aunque algo contraintuitivo, Little-o es la afirmació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 verdadero, pero f ∈ o (f) es falso. 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 g", mientras que "f ∈ o (g) significa que el crecimiento asintótico de f es estrictamente más lento que 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 se trabaja con notación O grande.

Sin embargo, para que f ∈ o (g) sea verdadera, entonces g debe incluir un mayor poder de x en su fórmula, por lo que la separación relativa entre f (x) yg (x) debe ser 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 lo sería 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³), (nuevamente, piense en O como <= y o como < )