lo hace O (N) significa

Question

Duplicar posible:
What is Big O notation? Do you use it?

Hola a todos,

bastante básico cuestión notación escalabilidad.

recientemente he recibido un comentario en un post que mi pitón ordenó lista implimentation "pero tenga cuidado de que su 'conjunto ordenado' ejecución es O (N) para las inserciones"

¿Qué es bueno saber, pero yo No estoy seguro de lo que esto significa.

que he visto notación tal como n (O) O (N), N (O-1) o N (O * O)

lo hace la notación anterior se refiere?

Answer 1

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

Brevemente:

1. O (1) significa en tiempo constante - independiente del número de elementos.
2. O (N) significa en proporción al número de artículos .
3. O (log N) significa un tiempo proporcional a log (N)

Básicamente cualquier notación 'O' significa una operación tomará tiempo hasta un máximo de k * f (N)
donde :

k es un multiplicador constante

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

Answer 2

Se llama Big O notación: http://en.wikipedia.org/wiki/Big_O_notation

Así diciendo que la inserción es O(n) significa que tienes que caminar a través de toda la lista (o la mitad de ella - gran notación O ignora factores constantes) para realizar la inserción.

Esto parece ser una buena introducción: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Answer 3

Esto puede ayudar:

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

O (n): Encontrar un elemento en una lista sin ordenar o un árbol mal formado (en el peor caso); agregando dos números de n dígitos

¡Buena suerte!

Answer 4

Wikipedia explains es mucho mejor que yo, sin embargo, significa que si su tamaño de lista es N, se necesita un máximo de N bucles/iteraciones para insertar un elemento. (En efecto, debe iterar sobre toda la lista)

Si quiere una mejor comprensión, hay un libro gratuito from Berkeley que profundiza la notación.

Answer 5

Específicamente O (n) significa que si hay 2x tantos elementos de la lista, que va a toma No más de el doble de tiempo, si hay 50 veces más que va a tomar No más que 50 veces más larga. Ver 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 tendrá lugar en most dos veces más larga, y si hay 50 veces más elementos, tomaría más 50 veces más larga.

Si fue adicionalmente Ω (n) (Big Omega de n), tomaría menos el doble de una lista que es el doble de grande.Si su implementación es tanto O (n) como Ω (n), lo que significa que tomará ambos en menos y en más el doble de una lista dos veces más grande, entonces se puede decir que es Θ (n) (Theta grande 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, siendo culpable de mí mismo) Big-O se utiliza a menudo donde Big-Theta es lo que se entiende. Sería técnicamente correcto llamar a tu función O (n^n^n^n) porque todo lo que Big-O dice es que tu función no es más lenta que eso, pero nadie diría eso más que para demostrar un punto porque es información no muy útil y engañosa, a pesar de ser técnicamente precisa.

Answer 6

Respuesta breve: 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: Ver los enlaces proporcionados por Ian P y dreeves

Answer 7

Se refiere a la complejidad de su programa es, es decir, el número de operaciones que se necesita para resolver realmente un problema. O (n) significa que cada operación toma el mismo número de pasos que los elementos en su lista, que para la inserción es muy lenta. Del mismo modo, si tiene O (n^2) significa que cualquier operación requiere "n" un número cuadrado de pasos para lograr, y así sucesivamente ... La "O" es para Orden de Magnitud, y la expresión entre paréntesis es siempre relacionado con la cantidad de elementos manipulados en el procedimiento.

Answer 8

O (n) es Big O Notation y se refiere a la complejidad de un algoritmo dado. n se refiere al tamaño de la entrada, en su caso es la cantidad de elementos en su lista.

O (n) significa que su algoritmo tomará el orden de n operaciones para insertar un elemento. p.ej. recorriendo la lista una vez (o una cantidad constante de veces, como dos veces o solo pasando por 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, lleva 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 ineficaces para manejar una gran cantidad de elementos.

Para las listas O (n) no es malo para la inserción, pero no es el más rápido. También tenga en cuenta que O (n/2) se considera que es lo mismo que O (n) porque ambos crecen a la misma velocidad con n.