explained - o notation sorting algorithms

¿Cuál es el significado de la memoria O(1), O(n), O(n*n)?

Question

Posible duplicado:
Explicación simple en inglés de Big O

Muchas veces, cuando se habla de la complejidad del tiempo de un algoritmo, la memoria también se tiene en cuenta. Quiero saber cuál es el significado de big-O (1), big-O (n), big-O (n * n) de memoria?

¿Y cómo se relaciona con la complejidad del tiempo?

Answer 1

Aquí todos han explicado el significado de la notación Big O. Entonces, no voy a explicar eso otra vez. Pero te explicaré en breve.

Tome cualquier programa pequeño en el que no hay bucles.

{ int a=1;
print("%d",a);
}

Este programa tomará un tiempo insignificante para ejecutar. Dejemos que la declaración y la impresión tomen una unidad de tiempo. Así que su complejidad en el tiempo será O (1).

Otro programa con un bucle y funcionando por n veces

{int a,i;
long n=10000000;
for(i=0;i<n;i++)
    // doing some calculations
}

Como se puede ver aquí, la declaración tomará un tiempo insignificante, es decir, O (1). Y si permitimos que la línea 4 tome una unidad de tiempo, es decir, O (n). Entonces, la complejidad global del tiempo será

O(1)+O(n)=O(n).

Ahora u puede entender para O (n * n), es decir, para 2 bucles.

Para un mejor entendimiento....

Encontrar un artículo en una lista sin clasificar = O (n)

Multiplicando dos números de n dígitos por un algoritmo simple o ordenación de burbuja = O (n * n)

Encontrar un elemento en una matriz ordenada con una búsqueda binaria = O (registro n)

Problema de vendedor con fuerza bruta = O (n!)

Answer 2

Como dijo xmoex:

o (1) constituye un uso de memoria constante. Así que la cantidad de entrada es intrascendente.

o (n) constituye un uso de memoria lineal. Así que más entrada significa linealmente más memoria.

o (n * n) constituye un uso de memoria cuadrática. Así que más entrada significa, cuadráticamente, más memoria (x ^ 2 en promedio.

Esta medida de la complejidad de la memoria en la mayoría de los casos es completamente independiente de la medida de la complejidad del tiempo. Para los algoritmos informáticos, es importante saber cómo el algoritmo administrará ambas complejidades para decidir la calidad del algoritmo. Sin embargo, ambos deben calcularse por separado. Uno puede ser más importante que el otro dependiendo de sus casos de uso y las circunstancias del problema.

Answer 3

La complejidad en términos de memoria significa la rapidez con la que se requiere el crecimiento del tamaño de la memoria al tiempo que crece una cantidad de elementos para procesar. Un buen ejemplo es el algoritmo de clasificación.

• O(1) y O(log n) significan que, mientras que la clasificación de N elementos, el algoritmo requiere menos memoria que la memoria total asignada para N elementos. (También conocido como clasificación en el lugar)
• O(n) : el consumo de memoria es lineal, por lo que el consumo de memoria aumenta a medida que los artículos cuentan con crecimiento
• O(n*n) significa que el algoritmo requiere mucha más memoria adicional.

Answer 4

No estoy seguro de que te refieras a big-O o little-O aquí, pero voy a responder de manera más general.

Significa lo mismo para la memoria que para el tiempo. Si una función crece en la memoria O (1), utiliza una cantidad constante de memoria independientemente del tamaño de entrada. Si una función crece en O (n) usa una cantidad lineal, y O (n * n) usa una cantidad cuadrática.

Answer 5

o (1) significa uso de memoria promedio constante, independientemente del tamaño de su entrada
o (n) significa que si tiene el elemento n que está procesando, su necesidad de memoria promedio se vuelve lineal
o (n * n) significa que si tiene n elementos que está procesando, su necesidad de memoria promedio aumentará de forma cuadrática

hay un artículo wiki sobre la llamada en.wikipedia.org/wiki/Big_O_notation (que también cubre poco o ...)