Estoy aprendiendo un curso de Coursera sobre la complejidad del tiempo. Me encuentro con esto en un vídeo y creo que algo anda mal. “Entonces supongamos que tenemos un algoritmo cuyo tiempo de ejecución es aproximadamente proporcional a n y queremos que lo ejecute en una máquina que funcione a aproximadamente un gigahercio. ¿Qué tan grande es la entrada que podemos manejar para que terminemos el cálculo en un segundo? ? ” (CPU de 1 GHZ (10 ^ 9 ciclos por segundo))
“Bueno, si se ejecuta aproximadamente en un tamaño n, puedes manejar alrededor de mil millones de entradas de tamaño, antes de que tarde más de un segundo” (10^9 / 10^9)
“Si se ejecuta como n al cuadrado, es mucho peor. Sólo puedes manejar entradas de un tamaño aproximado de 30.000 antes de que empiece a tardar más de un segundo”. n = 30000, (30000)^2/10^9 = 0,9 segundos ~ 1 segundo
“Si las entradas son de tamaño 2 elevado a n, es increíblemente malo, sólo puedes manejar entradas de tamaño aproximado 30 en un segundo” 2^30/10^9 ~ 1,07 seg
Con una complejidad de n log(n), si el tamaño de entrada n es 10^9, entonces debería tomar 10^9 * log(10^9) / 10^9 = 9 segundos, ¿verdad? De alguna manera muestra 30 segundos en el video. También decía que si n = 10^7,5 entonces el tiempo de ejecución es de 1 segundo, lo que también está mal en mi cálculo.
Calculé cada caso con la complejidad n, n^2, 2^n y todo estaba bien, solo el caso nlog(n) estaba en mal estado.
Aquí está la foto para más detalles: https://i.upanh.org/2022/04/11/nlogn.jpg[^]
Enlazado el video del curso (3:40 a 5:00 es la parte): https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
Edité la pregunta para que sea como en el video del curso que vi.
Lo que he probado:
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
Solución 1
Cita:Si el tamaño de entrada n es 10^9, entonces debería tomar 10^9 * log(10^9) / 10^9 = 9 segundos, ¿verdad?
No ! No se calcula el tiempo de ejecución a partir de la notación Big O, al menos no por sí sola.
La notación Big O le indica la complejidad de la categoría de un algoritmo, no el tiempo de ejecución, no directamente.
Cuando tiene un tiempo de ejecución para un tamaño de datos determinado, la complejidad de Big O le permite evaluar el tiempo de ejecución para otro tamaño de datos.
su tiempo de 1 segundo para datos de 20 a 10^6 significa que necesita cambiar a tiempo de milisegundos para obtener un tiempo significativo.
Solución 2
El gran O No da el tiempo exacto de ejecución. Ver, por ejemplo Notación O grande – Wikipedia[^] (Propiedades secciones, multiplicación por una constante).
Solución 3
Para agregar a lo que dicen los demás, de todos modos no se pueden equiparar los ciclos de reloj directamente con el tiempo de ejecución: algunas operaciones de la máquina requieren n ciclos para ejecutarse, otras pueden ser n * 2. Además, los procesadores modernos están canalizados, por lo que algunas instrucciones puede comenzar mientras otras se están ejecutando, almacenadas en caché, por lo que el tiempo de ejecución puede depender de cuánto tiempo hace que se ejecutó una instrucción por última vez y si sus datos están disponibles en las cachés L1, L2 o L3, la disponibilidad de núcleos libres para ejecutar, además de una gran cantidad de otros detalles.
No se puede simplemente decir “mi velocidad de reloj es X, por lo que mi tiempo de ejecución es X * Y”; hay muchos otros factores que influirán en ello.
Solución 5
30 segundos es lo correcto si es un registro2(norte). registro2(1000) ~= 10.
EDITAR: Los algoritmos O (n log (n)) a menudo dividen recursivamente el problema por la mitad, resuelven cada parte por separado y luego combinan las soluciones. Esta es la razón por la que iniciar sesión2 suele estar implícito. Mergesort es un buen ejemplo.
Solución 6
la notación O grande solo le dice cómo será el tiempo de ejecución cambiar cuando se cambia el “tamaño” del problema, no proporciona una estimación real para un caso específico.
En otras palabras, hay un factor desconocido, así por ejemplo O(n2) puede significar
time_needed = constant * n * n
donde nadie dice cuál es el valor de la constante, por lo tanto, no hay un valor concreto para time_needed.
El ejemplo sólo le dice que un problema dos veces más grande tardará cuatro veces más en resolverse.
コメント