year the significado seven nominados nation ganadores game elephant awards army album performance scalability big-o set

performance - the - ¿Qué significa O(N)



the game awards vote (8)

Posible duplicado:
¿Qué es la notación Big O? ¿Lo usas?

Hola a todos,

Pregunta bastante básica de notación de escalabilidad.

Hace poco recibí un comentario en una publicación que dice que mi implícita en la lista ordenada de Python "pero tenga en cuenta que su implementación ''conjunto ordenado es O (N) para inserciones"

Lo que es bueno saberlo, pero no estoy seguro de qué significa esto.

He visto notaciones como n (o) o (N), N (o-1) o N (o * o)

¿A qué se refiere la notación anterior?

El comentario se refería a la Notación Big-O .

Brevemente:

  1. O (1) significa en tiempo constante, independientemente del número de elementos.
  2. O (N) significa en proporción al número de artículos.
  3. O (registro N) significa un tiempo proporcional al registro (N)

Básicamente, cualquier notación ''O'' significa que una operación llevará tiempo hasta un máximo de k * f (N)
dónde:

k es un multiplicador constante

f () es una función que depende de N

Específicamente O (n) significa que si hay 2 veces más elementos en la lista, no tomará más del doble de tiempo, si hay 50 veces más no tomará más de 50 veces. Vea el artículo de wikipedia dreeves señalado para más detalles.

Editar (en negrita arriba): se señaló que Big-O representa el límite superior, por lo que si hay el doble de elementos en la lista, la inserción tomará a lo sumo el doble, y si hay 50 veces más elementos, tardaría a lo sumo 50 veces más tiempo.

Si además fuera Ω (n) (Big Omega de n), entonces tomaría al menos el doble de tiempo para una lista que es el doble de grande. Si su implementación es O (n) y Ω (n), lo que significa que tomará tanto al menos como el doble de una lista el doble de grande, entonces se puede decir que es Θ (n) (Gran Theta de n), lo que significa que tomará exactamente el doble de tiempo si hay el doble de elementos.

De acuerdo con Wikipedia (y la experiencia personal, al ser culpable) Big-O se usa a menudo donde Big-Theta es lo que significa. Sería técnicamente correcto llamar a su función O (n ^ n ^ n ^ n) porque todo lo que dice Big-O es que su función no es más lenta que eso, pero nadie diría eso aparte de probar un punto porque es Información no muy útil y engañosa, a pesar de ser técnicamente precisa.

O (n) es la notación O grande y se refiere a la complejidad de un algoritmo dado. n se refiere al tamaño de la entrada, en su caso, es el número de elementos en su lista.

O (n) significa que su algoritmo tomará el orden de n operaciones para insertar un elemento. por ejemplo, repasar la lista una vez (o un número constante de veces, como dos o solo recortar la mitad).

O (1) significa que lleva un tiempo constante, que no depende de cuántos elementos hay en la lista.

O (n ^ 2) significa que para cada inserción, toma n * n operaciones. es decir, 1 operación para 1 artículo, 4 operaciones para 2 artículos, 9 operaciones para 3 artículos. Como puede ver, los algoritmos O (n ^ 2) se vuelven ineficientes para manejar una gran cantidad de elementos.

Para las listas O (n) no está mal para la inserción, pero no la más rápida. También tenga en cuenta que O (n / 2) se considera igual a O (n) porque ambos crecen a la misma velocidad que n.

Respuesta corta: Significa que el tiempo de procesamiento está en relación lineal con el tamaño de la entrada. Por ejemplo, si el tamaño de la entrada (longitud de la lista) se triplica, el tiempo de procesamiento (aproximadamente) se triplica. Y si aumenta mil veces, el tiempo de procesamiento también aumenta en la misma magnitud.

Respuesta larga: vea los enlaces proporcionados por Ian P y dreeves

Se refiere a qué tan complejo es su programa, es decir, cuántas operaciones se requieren para resolver un problema. O (n) significa que cada operación toma la misma cantidad de pasos que los elementos en su lista, que para la inserción, es muy lento. Del mismo modo, si tiene O (n ^ 2) significa que cualquier operación requiere "n" un número cuadrado de pasos para realizar, y así sucesivamente ... La "O" es para Orden de Magnitud, y la expresión entre paréntesis es Siempre relacionado con el número de elementos que se manipulan en el procedimiento.

Big-O mucho mejor que yo, sin embargo, significa que si el tamaño de tu lista es N, se necesitan en el máximo N bucles / iteraciones para insertar un elemento. (En efecto, tienes que iterar sobre toda la lista)

Si desea una mejor comprensión, hay un libro gratuito de Berkeley que profundiza más sobre la notación.