De acuerdo, sé que Mergesort tiene el peor momento de Theta (NlogN), pero su sobrecarga es alta y se manifiesta cerca de la parte inferior del árbol de recursión donde se realizan las fusiones. Alguien propuso que detengamos la recursión una vez que el tamaño llegue a K y cambiemos al género de inserción en ese punto. Necesito demostrar que el tiempo de ejecución de esta relación de recurrencia modificada es theta (NK + Nlog (N/k))? Estoy en blanco sobre cómo abordar este problema.¿Demostrar el tiempo de ejecución de mergesort optimizado es theta (NK + Nlog (N/K))?
Respuesta
Quizás un buen comienzo sea ver la relación de recurrencia para este problema. Imagino para mergesort típica se vería algo como esto:
T(N) = 2 * T(N/2) + N
es decir, estás dividiendo el problema en subproblemas 2 de la mitad del tamaño, y luego realizar el trabajo N (la fusión). Tenemos un caso base que lleva tiempo constante.
Modelado esto como un árbol que tenemos:
T(N) = N -> T(N/2)
-> T(N/2)
= N -> (N/2) -> T(N/4)
-> T(N/4)
-> (N/2) -> T(N/4)
-> T(N/4)
Esto da una expansión de
T(N) = N + 2N/2 + 4N/4 + ...
= N + N + N ...
Así que en realidad sólo tenemos que ver qué tan profundo que va. Sabemos que el nivel i
está en los subproblemas N/2^i
. Así que nuestros nodos hoja (T(1)
) se producen en el nivel L
donde N/2^L = 1
:
N/2^L = 1
N = 2^L
log N = log(2^L)
log N = L
Así que nuestro tiempo de ejecución es N log N
.
Ahora presentamos la ordenación por inserción. Nuestro árbol se verá algo como esto
T(N) = ... -> I(K)
-> I(K)
...x N/K
En otras palabras, vamos a en algún nivel L
tienen que resolver los problemas de inserción N/K
especie de tamaño K
. La ordenación por inserción tiene un tiempo de ejecución en el peor de los casos de K^2
. Así que en las hojas que tienen esta cantidad de trabajo en total :
(N/K) * I(K)
= (N/K) * K * K
= N * K
Pero también tenemos un montón de fusión que hacer, así, a un costo de N
por cada nivel del árbol como se ha explicado antes. Volviendo a nuestro método anterior, vamos a averiguar L
(el número de niveles antes de llegar a subproblemas de tamaño K
y por lo tanto cambiar a la inserción):
N/2^L = K
N/K = 2^L
L = log (N/K)
Así que en total tenemos
O(N) = N * K + N * log (N/K)
Ha sido demasiado tiempo desde que tomé algoritmos para darte un boceto a prueba, pero eso debería hacer que tus neuronas se activen.
- 1. Tomar una instantánea del tiempo de ejecución optimizado de JVM
- 2. Agregar/eliminar archivos de registro durante el tiempo de ejecución en NLog
- 3. ¿Qué es el tiempo de ejecución moderno?
- 4. Etiqueta del eje Matplotlib: \ theta no funciona \ Theta does
- 5. ¿Por qué es mejor el mergesort para listas enlazadas?
- 6. ¿Cuál es el tiempo de ejecución de este algoritmo powerset
- 7. ¿Qué es el entorno de tiempo de ejecución?
- 8. FederatedAuthentication.WSFederationAuthenticationModule es nulo en tiempo de ejecución
- 9. Quicksort más lento que Mergesort?
- 10. Quicksort multiproceso o mergesort
- 11. ¿El genérico es el tiempo de ejecución o el tiempo de compilación del polimorfismo?
- 12. ¿Qué es el tiempo de ejecución y el polimorfismo de tiempo de compilación?
- 13. ¿Cuál es el mejor visor para NLog?
- 14. ¿Por qué NumberFormatException es el tiempo de ejecución?
- 15. .NET optimizado Int32
- 16. ¿En el tiempo de diseño, el paquete uri es válido, pero no en tiempo de ejecución?
- 17. cómo ver el código optimizado en c
- 18. NLog formato de hora
- 19. reconfigurando NLog programáticamente
- 20. Tiempo promedio de ejecución
- 21. Mida el tiempo de ejecución en C#
- 22. desactivar el tiempo de ejecución datagridviewcombobox
- 23. La sobrecarga es tiempo de compilación en tiempo de ejecución y de la anulación es?
- 24. quicksort e inserción ordenar el tiempo de espera esperado híbrido
- 25. Delphi Project Necesita paquetes de tiempo de ejecución, incluso con el tiempo de ejecución Paquetes desactivados
- 26. Cargando jar en el tiempo de ejecución
- 27. El tiempo máximo de ejecución en phpMyadmin
- 28. tiempo de ejecución de mysql
- 29. No es seguro buscar datos de tiempo de ejecución objc
- 30. tiempo de ejecución "real" límite