Cuál es la diferencia entre Big-O notación O(n) y Poco-O notación o(n)?
Respuestas
337 para la respuesta № 1f ∈ O (g) dice, esencialmente
por al menos uno elección de una constante k > 0, puedes encontrar una constante un de modo que la desigualdad 0 <= f (x) <= k g (x) se cumple 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
por cada elección de una constante k > 0, puedes encontrar una constante un de modo que la desigualdad 0 <= f (x) <k g (x) se cumple 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 particular k Para lo cual la desigualdad se mantiene más allá de algún mínimo. X.
En Little-o, debe ser que haya un mínimo X después de lo cual la desigualdad se mantiene, no importa lo pequeña que hagas k, siempre y cuando no sea negativo o cero.
Estos dos describen los límites superiores, aunquealgo 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 no es más rápido que g" s ", mientras que" f ∈ o (g) significa que el crecimiento asintótico de f "es estrictamente más lento que g "s". 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 notación de gran O.
Sin embargo, para que f ∈ o (g) sea verdadero, entonces g debe incluir un valor más alto. poder de x en su fórmula, por lo que la separación relativa entre f (x) y g (x) en realidad 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). p.ej. x² ∈ o (x³), por lo que también es cierto que x² ∈ O (x³), (nuevamente, piense en O como <= y o como <)
160 para la respuesta № 2
Big-O es a poco-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,< 2y≤ 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 estar en términos de 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 puede decir cosas como nO (1) = P.
29 para la respuesta № 3
Encuentro que cuando no puedo captar algo conceptualmente, pensando por qué uno usaría X Es útil entender a X. (No quiere decir que no hayas intentado eso, simplemente estoy preparando el escenario).
[cosas que sabes] Una forma común de clasificarlos algoritmos son por tiempo de ejecución, y al citar la gran 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 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 un 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 (norte⁄loglogloglogN). ¡HURRA! ¡Es mas rapido! Pero se sentiría tonto al escribir eso una y otra vez cuando esté escribiendo su 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 :)