¿Prueba el tiempo de ejecución de Mergesort optimizado es Theta (NK + NLOG (N/K))?

Question

De acuerdo, sé que Mergesort tiene el peor de los casos de theta (NLOGN), pero su sobrecarga es alta y se manifiesta cerca del fondo del árbol de recursiones donde se hacen las fusiones. Alguien propuso que detuviéramos la recursión una vez que el tamaño alcanza K y cambia a la clasificación 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 bloqueando cómo abordar este problema.

Answer 1

Tal vez un buen comienzo es mirar la relación de recurrencia para este problema. Me imagino que para la típica mergesort se vería algo así:

T(N) = 2 * T(N / 2) + N

es decir, estás dividiendo el problema en 2 subproblemas de la mitad del tamaño, y luego realizando n trabajo (la fusión). Tenemos un caso base que lleva tiempo constante.

Modelando 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 realmente solo necesitamos ver qué tan profundo va. Sabemos que el iEl nivel de TH opera en subproblemas N / 2^i en tamaño. Entonces nuestros nodos de hoja (T(1)) ocurre en el nivel L dónde N / 2^L = 1:

N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L

Entonces nuestro tiempo de ejecución es N log N.

Ahora presentamos el orden de inserción. Nuestro árbol se verá como esto

T(N) = ... -> I(K)
           -> I(K)
             ...x N/K

En otras palabras, lo haremos en algún nivel L tener que resolver N/K Inserción Ordenar problemas de tamaño K. El tipo de inserción tiene el peor de tiempo de ejecución de K^2. Entonces, en las hojas tenemos tanto trabajo en total:

(N / K) * I(K)
= (N / K) * K * K
= N * K

Pero también tenemos un montón de fusiones que hacer también, a un costo de N por nivel del árbol como se explicó anteriormente. Volviendo a nuestro método anterior, encontremos L (el número de niveles antes de alcanzar subproblemas de tamaño K y así cambiar a la inserción):

N / 2^L = K
N / K = 2^L
L = log (N/K)

Entonces en total tenemos

O(N) = N * K + N * log (N/K)

Ha pasado demasiado tiempo desde que tomé algoritmos para darle un boceto de prueba, pero eso debería hacer que sus neuronas disparen.