Prove que o tempo de execução do mergesort otimizado é theta (NK + Nlog (N / K))?

Question

Ok, eu sei que o Mergesort tem o pior caso de tempo de theta (NlogN), mas sua sobrecarga é alta e se manifesta perto da parte inferior da árvore de recursão onde as mesclagens são feitas.Alguém propôs que parássemos a recursão assim que o tamanho atingir K e mudássemos para a classificação por inserção nesse ponto.Preciso provar que o tempo de execução dessa relação de recorrência modificada é theta (NK + Nlog (N / k))?Estou sem saber como abordar este problema.

Answer 1

Talvez um bom começo seja olhar para a relação de recorrência desse problema. Eu imagino que para mergesort típico seria algo assim:

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

ou seja, você está dividindo o problema em 2 subproblemas da metade do tamanho e, em seguida, executando N trabalho (a fusão). Temos um caso base que leva tempo constante.

Modelando isso como uma árvore, temos:

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)

Isso dá uma expansão de

T(N) = N + 2N/2 + 4N/4 + ...
     = N + N + N ...

Então, na verdade, só precisamos ver até onde vai. Sabemos que o nível ith opera em subproblemas N / 2^i em tamanho. Portanto, nossos nós folha (T(1)) ocorrem no nível L, onde N / 2^L = 1:

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

Portanto, nosso tempo de execução é N log N.

Agora apresentamos a classificação por inserção. Nossa árvore será parecida com esta

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

Em outras palavras, iremos em algum nível L ter que resolver problemas de classificação por inserção de N/K de tamanho K. A classificação de inserção tem um tempo de execução de pior caso de K^2. Portanto, nas folhas, temos muito trabalho no total :

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

Mas também temos um monte de fusões para fazer, ao custo de N por nível da árvore, conforme explicado antes. Voltando ao nosso método anterior, vamos encontrar L (o número de níveis antes de alcançarmos os subproblemas de tamanho K e, assim, mudar para a inserção):

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

Portanto, no total, temos

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

Já faz muito tempo desde que usei algoritmos para fornecer um esboço de prova, mas isso deve fazer seus neurônios dispararem.