algorithm - rapper - ¿Por qué la constante siempre se elimina del gran análisis O?
big o rapper (5)
Big O sin constante es suficiente para el análisis de algoritmos.
En primer lugar, el tiempo real no solo depende de cuántas instrucciones, sino también del tiempo de cada instrucción, que está estrechamente relacionado con la plataforma donde se ejecuta el código. Es más que un análisis teórico. Entonces la constante no es necesaria para la mayoría de los casos.
En segundo lugar, Big O se usa principalmente para medir cómo aumentará el tiempo de ejecución a medida que el problema aumenta o cómo disminuye el tiempo de ejecución a medida que mejora el rendimiento del hardware.
En tercer lugar, para situaciones de optimización de alto rendimiento, constante también se tendrá en cuenta.
Estoy tratando de comprender un aspecto particular del análisis de Big O en el contexto de ejecutar programas en una PC.
Supongamos que tengo un algoritmo que tiene un rendimiento de O (n + 2). Aquí si n se pone realmente grande, el 2 se vuelve insignificante. En este caso, está perfectamente claro que el rendimiento real es O (n).
Sin embargo, supongamos que otro algoritmo tiene un rendimiento promedio de O (n ^ 2/2). El libro donde vi este ejemplo dice que el rendimiento real es O (n ^ 2). No estoy seguro de entender por qué, me refiero a que el 2 en este caso no parece completamente insignificante. Así que estaba buscando una explicación clara del libro. El libro lo explica de esta manera:
"Considere sin embargo lo que significa 1/2. El tiempo real para verificar cada valor depende en gran medida de la instrucción de la máquina que el código traduce y luego de la velocidad a la que la CPU puede ejecutar las instrucciones. Por lo tanto, el 1/2 doesn '' significa mucho ".
Y mi reacción es ... ¿Huh? Literalmente, no tengo ni idea de qué dice eso ni más concretamente qué tiene que ver esa afirmación con su conclusión. ¿Alguien puede deletrearlo por favor?
Gracias por cualquier ayuda.
El tiempo requerido para realizar una tarea en particular en las computadoras actualmente no requiere una gran cantidad de tiempo a menos que el valor ingresado sea muy grande.
Supongamos que queremos multiplicar 2 matrices de tamaño 10 * 10, no tendremos problemas a menos que deseemos realizar esta operación varias veces y luego prevalezca el papel de las notaciones asintóticas y cuando el valor de n sea muy grande, las constantes no realmente hace alguna diferencia a la respuesta y son casi insignificantes, por lo que tendemos a dejarlos mientras calculamos la complejidad.
La notación de Big-O no se preocupa por las constantes porque la notación de O grande solo describe la tasa de crecimiento a largo plazo de las funciones, en lugar de sus magnitudes absolutas. Multiplicar una función por una constante solo influye en su tasa de crecimiento en una cantidad constante, por lo que las funciones lineales aún crecen linealmente, las funciones logarítmicas aún crecen logarítmicamente, las funciones exponenciales aún crecen exponencialmente, etc. Como estas categorías no se ven afectadas por constantes, no lo hace importa que dejemos caer las constantes.
¡Dicho eso, esas constantes son absolutamente significativas! Una función cuyo tiempo de ejecución es 10 100 n será mucho más lenta que una función cuyo tiempo de ejecución sea solo n. Una función cuyo tiempo de ejecución es n 2/2 será más rápida que una función cuyo tiempo de ejecución sea solo n 2 . El hecho de que las dos primeras funciones sean O (n) y las otras dos sean O (n 2 ) no cambia el hecho de que no se ejecutan en la misma cantidad de tiempo, ya que esa no es la notación de la gran O está diseñado para. La notación O es buena para determinar si a largo plazo una función será más grande que otra. Aunque 10 100 n es un valor colosalmente enorme para cualquier n> 0, esa función es O (n) y, por lo tanto, para n lo suficientemente grande eventualmente superará a la función cuyo tiempo de ejecución es n 2/2 porque esa función es O (n 2 )
En resumen, como big-O solo habla de clases relativas de tasas de crecimiento, ignora el factor constante. Sin embargo, esas constantes son absolutamente significativas; simplemente no son relevantes para un análisis asintótico.
¡Espero que esto ayude!
La notación de Big-O solo describe la tasa de crecimiento de los algoritmos en términos de función matemática, en lugar del tiempo real de ejecución de los algoritmos en alguna máquina.
Matemáticamente, Sean f (x) yg (x) positivos para x lo suficientemente grande. Decimos que f (x) y g (x) crecen a la misma velocidad que x tiende a infinito, si
ahora vamos a f (x) = x ^ 2 yg (x) = x ^ 2/2, luego lim (x-> infinito) f (x) / g (x) = 2. entonces x ^ 2 y x ^ 2/2 tienen la misma tasa de crecimiento. Así que podemos decir O (x ^ 2/2) = O (x ^ 2).
Como dijo templatetypedef, las constantes ocultas en notaciones asintóticas son absolutamente significativas. Como ejemplo: marge sort se ejecuta en O (nlogn) el peor de los casos y la ordenación de inserción se ejecuta en O (n ^ 2) el peor de los casos. Pero los factores constantes ocultos en la ordenación de inserción es más pequeña que la de marge sort, en la práctica, la ordenación por inserción puede ser más rápida que la ordenación marge para tamaños de problema pequeños en muchas máquinas.
Tienes toda la razón de que las constantes importan. Al comparar muchos algoritmos diferentes para el mismo problema, los números O sin constantes le dan una visión general de cómo se comparan entre sí. Si luego tiene dos algoritmos en la misma clase O, los compararía usando las constantes involucradas.
Pero incluso para diferentes clases O las constantes son importantes. Por ejemplo, para multidigital o multiplicación de enteros grandes, el algoritmo ingenuo es O (n ^ 2), Karatsuba es O (n ^ log_2 (3)), Toom-Cook O (n ^ log_3 (5)) y Schönhage-Strassen O (n * log (n) * log (log (n))). Sin embargo, cada uno de los algoritmos más rápidos tiene una sobrecarga cada vez mayor reflejada en constantes grandes. Entonces, para obtener puntos de cruce aproximados, se necesitan estimaciones válidas de esas constantes. Así, uno obtiene, como SWAG, que hasta n = 16 la multiplicación ingenua es la más rápida, hasta n = 50 Karatsuba y el cruzamiento de Toom-Cook a Schönhage-Strassen ocurre para n = 200.
En realidad, los puntos de cruce no solo dependen de las constantes, sino también del caché del procesador y otros problemas relacionados con el hardware.