Gran O Pregunta sobre un algoritmo con (n ^ 2 + n) / 2 tasa de crecimiento

Estoy haciendo esta pregunta porque estoy confundido acerca de un aspecto con respecto a la notación O grande.

Estoy usando el libro, Estructuras de datos y abstracciones con Java de Frank Carrano. En el capítulo sobre "Eficiencia de los algoritmos", muestra el siguiente algoritmo:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

Inicialmente describe este algoritmo como teniendo una tasa de crecimiento de ^{(n 2  + n)} / ₂ . Que mirarlo parece intuitivo.

Sin embargo, se afirma que ^{(n 2  + n)} / _{2 se} comporta como n ² cuando n es grande. En el mismo párrafo se afirma ^{(n 2  + n)} / ₂ también se comporta como ^{n 2} / ₂ . Él usa esto para clasificar el algoritmo anterior como O (n ² ) .

Entiendo que ^{(n 2  + n)} / ₂ es similar a la ^{n 2} / ₂ , porque porcentualmente, n hay mucha diferencia. Lo que no entiendo es por qué ^{(n 2  + n)} / ₂ y N ² son similares, cuando n es grande.

Por ejemplo, si n = 1,000,000 :

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

Ese último no es similar en absoluto. De hecho, obviamente, es el doble que el del medio. Entonces, ¿cómo puede Frank Carrano decir que son similares? Además, cómo se clasifica el algoritmo como O (n ² ) . Mirando ese circuito interno, diría que fue n ² + ⁿ / ₂

Al calcular la complejidad Big-O de un algoritmo, lo que se muestra es el factor que da la mayor contribución al aumento en el tiempo de ejecución si aumenta el número de elementos sobre los que ejecuta el algoritmo.

Si tiene un algoritmo con una complejidad de (n^2 + n)/2y duplica el número de elementos, entonces la constante 2no afecta el aumento en el tiempo de ejecución, el término nprovoca una duplicación en el tiempo de ejecución y el término n^2provoca un aumento de cuatro veces en la ejecución hora.
Como el n^2término tiene la mayor contribución, la complejidad de Big-O es O(n^2).

La definición es que

f(n) = O(g(n))

si existe alguna constante C> 0 tal que, para todas las n mayores que algunas n_0, tenemos

|f(n)| <= C * |g(n)|

Esto es claramente cierto para f (n) = n ^ 2 y g (n) = 1/2 n ^ 2, donde la constante C debería ser 2. También es fácil ver que es cierto para f (n) = n ^ 2 yg (n) = 1/2 (n ^ 2 + n).

Cuando se habla de complejidad, solo le interesan los cambios en el factor tiempo basados ​​en el número de elementos ( n).

Como tal, puede eliminar cualquier factor constante (como el 2aquí).

Esto te deja con O(n^2 + n).

Ahora, para un producto razonablemente grande n, es decir n * n, será significativamente más grande que solo n, que es la razón por la que también puedes omitir esa parte, lo que te deja con una complejidad final O(n^2).

Es cierto, para números pequeños habrá una diferencia significativa, pero esto se vuelve más marginal cuanto más grande se nvuelve.

No es que "(n² + n) / 2 se comporte como n² cuando n es grande", es que (n² + n) / 2 crece como n² a medida que n aumenta .

Por ejemplo, a medida que n aumenta de 1,000 a 1,000,000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Del mismo modo, a medida que n aumenta de 1,000,000 a 1,000,000,000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Crecen de manera similar, de eso se trata Big O Notation.

Si trazas (n² + n) / 2 y n² / 2 en Wolfram Alpha , son tan similares que son difíciles de distinguir por n = 100. Si traza los tres en Wolfram Alpha , verá dos líneas separadas por un factor constante de 2.

Parece que necesitas resolver un poco más la notación O grande . Cuán conveniente es esta notación, es muy engañosa debido al uso de un signo igual, que no se usa aquí para denotar la igualdad de funciones.

Como saben, esta notación expresa una comparación asintótica de funciones, y escribir f = O (g) significa que f (n) crece como máximo tan rápido como g (n) cuando n llega al infinito. Una manera simple de traducir esto es decir que la función f / g está acotada. Pero, por supuesto, tenemos que ocuparnos de los lugares donde g es cero y terminamos con la definición más sólida que se puede leer en casi todas partes .

Esta notación resulta muy conveniente para la informática, es por eso que está tan extendida, pero debe manejarse con cuidado ya que el signo igual que vemos allí no denota una igualdad de funciones . Esto es más o menos como decir que 2 = 5 mod 3 no implica que 2 = 5 y si estás interesado en álgebra, puedes entender la gran notación O como un módulo de igualdad algo.

Ahora, para volver a su pregunta específica, es totalmente inútil calcular algunos valores numéricos y compararlos: por grande que sea un millón, no tiene en cuenta el comportamiento asintótico. Sería más útil trazar la relación de las funciones f (n) = n (n-1) / 2 y g (n) = n² , pero en este caso especial podemos ver fácilmente que f (n) / g (n) es menor que 1/2 si n> 0, lo que implica que f = O (g) .

Para mejorar su comprensión de la notación, debe

• Trabaje con una definición limpia, no con una impresión borrosa basada en cosas similares , tal como lo acaba de experimentar, una impresión borrosa no funciona bien.

• Tómese un tiempo para resolver ejemplos en detalle. Si trabaja tan solo cinco ejemplos en una semana, será suficiente para mejorar su confianza. Este es un esfuerzo que definitivamente vale la pena.

Nota algebraica secundaria Si A es el álgebra de todas las funciones Ν → Ν y C, el subalgebra de las funciones limitadas, dada una función f, el conjunto de funciones que pertenecen a O (f) es un submódulo C de A , y las reglas de cálculo en el gran La notación O simplemente describe cómo A opera en estos submódulos. Por lo tanto, la igualdad que vemos es una igualdad de submódulos C de A , este es solo otro tipo de módulo.

Creo que no entiendes lo que significa la gran notación O.

Cuando vea O (N ^ 2) básicamente significa: cuando el problema se vuelve 10 veces mayor, el tiempo para resolverlo será: 10 ^ 2 = 100 veces mayor.

Pongamos 1000 y 10000 en tu ecuación: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Entonces, mientras que la N era 10 veces más grande, las soluciones eran 100 veces más grandes. Por lo tanto se comporta: O (N ^ 2)

si n fuera un 1,000,000entonces

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 ¿qué?

Si bien la complejidad nos brinda una forma de predecir un costo en el mundo real (segundos o bytes dependiendo de si estamos hablando de la complejidad del tiempo o la complejidad del espacio), no nos da una cantidad de segundos ni ninguna otra unidad en particular.

Nos da un grado de proporción.

Si un algoritmo tiene que hacer algo n² veces, entonces tomará n² × c para un valor de c que es el tiempo que toma cada iteración.

Si un algoritmo tiene que hacer algo n² ÷ 2 veces, tomará n² × c para un valor de c que sea el doble del tiempo que toma cada iteración.

De cualquier manera, el tiempo empleado sigue siendo proporcional a n².

Ahora, estos factores constantes no son algo que podamos ignorar; de hecho, puede tener el caso en el que un algoritmo con complejidad O (n²) funciona mejor que uno con complejidad O (n), porque si estamos trabajando en un pequeño número de elementos, el impacto de los factores consistentes es mayor y puede abrumar otras preocupaciones . (De hecho, incluso O (n!) Es lo mismo que O (1) para valores suficientemente bajos de n).

Pero no son de lo que nos dice la complejidad.

En la práctica, hay algunas maneras diferentes en que podemos mejorar el rendimiento de un algoritmo:

1. Mejore la eficiencia de cada iteración: O (n²) todavía se ejecuta en n² × c segundos, pero c es más pequeño.
2. Reduzca el número de casos vistos: O (n²) todavía se ejecuta en n² × c segundos, pero n es más pequeño.
3. Reemplace el algoritmo con uno que tenga los mismos resultados, pero de menor complejidad: por ejemplo, si pudiéramos volver a convertir algo O (n²) en algo O (n log n) y, por lo tanto, cambiar de n² × c₀ segundos a (n log n) × c₁ segundos .

O, para verlo de otra manera, tenemos f(n)×csegundos tomados y puede mejorar el rendimiento reduciendo c, reduciendo no reduciendo lo que fdevuelve un determinado n.

Lo primero que podemos hacer mediante algunas microopciones dentro de un bucle, o usando un mejor hardware. Siempre dará una mejora.

Lo segundo que podemos hacer es quizás identificando un caso en el que podamos cortocircuitar el algoritmo antes de que todo sea examinado, o filtrar algunos datos que no serán significativos. No dará una mejora si el costo de hacerlo supera la ganancia, pero generalmente será una mejora mayor que el primer caso, especialmente con una n grande.

El tercero lo podemos hacer usando un algoritmo completamente diferente. Un ejemplo clásico sería reemplazar una ordenación de burbujas con una clasificación rápida. Con un número bajo de elementos, podríamos haber empeorado las cosas (si c₁ es mayor que c₀), pero generalmente permite las mayores ganancias, especialmente con n muy grande.

En el uso práctico, las medidas de complejidad nos permiten razonar sobre las diferencias entre los algoritmos precisamente porque ignoran la cuestión de cómo ayudaría reducir nc, para concentrarnos en examinar f()

Factor constante

El punto de la notación O grande es que puede elegir un factor constante arbitrariamente grande para que O (función (n)) sea siempre mayor que la función C * (n). Si el algoritmo A es mil millones de veces más lento que el algoritmo B, entonces tienen la misma complejidad O, siempre que esa diferencia no crezca cuando n crece arbitrariamente grande.

Supongamos un factor constante de 1000000 para ilustrar el concepto: es un millón de veces más grande que lo necesario, pero eso ilustra el punto de que se consideran irrelevantes.

(n ^ 2 + n) / 2 "cabe dentro" O (n ^ 2) porque para cualquier n, no importa cuán grande sea, (n ^ 2 + n) / 2 <1000000 * n ^ 2.

(n ^ 2 + n) / 2 "no se ajusta" a un conjunto más pequeño, por ejemplo, O (n) porque para algunos valores (n ^ 2 + n) / 2> 1000000 * n.

Los factores constantes pueden ser arbitrariamente grandes: un algoritmo con un tiempo de ejecución de n años tiene una complejidad O (n) que es "mejor" que un algoritmo con un tiempo de ejecución de n * log (n) microsegundos.

Big-O se trata de "cuán complicado" es un algoritmo. Si tiene dos algoritmos, y uno tarda unos n^2*ksegundos en ejecutarse, y el otro tarda unos n^2*jsegundos en ejecutarse, entonces puede discutir cuál es mejor, y podría hacer algunas optimizaciones interesantes para tratar de afectar ko j, pero ambas estos algoritmos son muy lentos en comparación con un algoritmo que se necesita n*mpara ejecutar No importa cuán pequeñas sean las constantes ko j, para una entrada lo suficientemente grande, el n*malgoritmo siempre ganará, incluso si mes bastante grande.

Entonces llamamos a los dos primeros algoritmos O(n^2), y llamamos al segundo O(n). Divide muy bien el mundo en clases de algoritmos. De esto se trata big-O. Es como dividir los vehículos en automóviles, camiones y autobuses, etc. Hay muchas variaciones entre los automóviles, y puede pasar todo el día discutiendo si un Prius es mejor que un Chevy Volt, pero al final del día si necesita poner a 12 personas en una, entonces este es un argumento bastante insensato. :)