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

Question

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

Answer 1

f ∈ O (g) dice, esencialmente

  

al menos un elección de una constante k > 0, se puede encontrar una constante a tales que la desigualdad 0 <= f (x) <= kg (x) es válida 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

  

cada elección de una constante k > 0, se puede encontrar una constante a tales que la desigualdad 0 <= f (x ) a.

Una vez más, obsérvese que o (g) es un conjunto.

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

En poco-o, debe ser que hay un mínimo x después de lo cual la desigualdad no se sostiene por pequeña que usted hace k , con tal de que no es negativo o cero.

Estos ambos describen los límites superiores, aunque un poco contra-intuitivo, Little-o es la declaración más fuerte. Hay un espacio mucho más grande entre las tasas de crecimiento de f y g si f ∈ O (g) que si f ∈ O (g).

Un ejemplo de la disparidad es la siguiente: f ∈ O (f) es cierto, pero f ∈ O (f) es falsa. Por lo tanto, Big-O se puede leer como "f ∈ O (g) significa que el crecimiento asintótico de f no más rápido que g de es", mientras que "f ∈ O (g) significa que el crecimiento asintótico de f es estrictamente más lento que g de". Es como <= frente <.

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 cierto. Es por esto que se puede soltar constantes cuando se trabaja con la notación de orden O.

Sin embargo, para f ∈ O (g) a ser verdad, entonces g debe incluir un mayor potencia de x en su fórmula, y la separación por lo que la relación entre f (x) y g (x ) en realidad debe ser más grande cuando x se hace más grande.

Para utilizar ejemplos puramente matemáticas (en lugar de referirse a los algoritmos):

El siguiente es cierto para Big-O, pero no sería cierto si se ha utilizado poco-o:

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

El siguiente es cierto para el pequeño-o:

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

Tenga en cuenta que si f ∈ O (g), esto implica f ∈ O (g). p.ej. x² ∈ O (x ³) por lo que también es cierto que x² ∈ O (x ³), (de nuevo, pensar en O como <= y o como <)

Answer 2

Big-O es poco-o como ≤ es <. Big-O es un límite superior inclusive, mientras que poco-o es un estricto límite superior.

Por ejemplo, el f(n) = 3n función es:

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

Análogamente, la 1 número 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 debe haber límite en cuanto a la < . / a> en lugar del límite normal Por ejemplo, 3 + (n mod 2) oscila entre 3 y 4 siempre es en O(1) pesar de no tener un límite normal, porque todavía tiene un lim sup:.. 4)

Te recomiendo memorizar la forma en la notación Big-O convierte a las comparaciones asintótica. Las comparaciones son más fáciles de recordar, pero menos flexible porque no se puede decir cosas como n ^{O (1)} = P.

Answer 3

Me parece que cuando no puedo entender conceptualmente algo, pensando en por qué se podría utilizar X es útil para entender X. (No quiere decir que usted no ha probado que, sólo soy preparando el escenario.)

[materia que usted sabe] Una forma común de clasificar los algoritmos es por el tiempo de ejecución, y mediante la mención de la complejidad del grande-Oh de un algoritmo, se puede obtener una buena estimación de los cuales uno es "mejor" - el que tiene la " más pequeña función" en el O! Incluso en el mundo real, O (N) es "mejor" que O (N ²), salvo cosas tontas como constantes supermasivos y similares. [/ Materia que usted sabe]

Digamos que hay algún algoritmo que se ejecuta en O (N). Bastante bueno, ¿eh? Pero digamos que usted (brillante persona,) a subir con un algoritmo que se ejecuta en O ( ^N / _{loglogloglogN} ). ¡HURRA! ¡Es mas rapido! Pero se sentiría la escritura tonta que una y otra vez cuando usted está escribiendo su tesis. Así se escribe una vez y se puede decir "En este trabajo, he demostrado que el algoritmo X, previamente computable en tiempo O (N), es de hecho computable en O (n)."

Por lo tanto, todo el mundo sabe que su algoritmo es más rápido --- por la cantidad no está clara, pero saben que es más rápido. En teoría. :)