Diferencia entre Big-O y Little-O notación
-
21-09-2019 - |
Pregunta
¿Cuál es la diferencia entre Big O- O(n)
notación y Little-O o(n)
notación?
Solución
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 <
)
Otros consejos
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²)
yO(n)
- No en
O(lg n)
,o(lg n)
oo(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.
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. :)