Pior caso, tempo de execução de classificação lexicográfica de uma lista de n strings, cada uma de comprimento n, usando classificação por mesclagem

Question

Esta mesma pergunta foi feita aqui tantas vezes por diversas pessoas.Esse é um problema que foi questionado em um vestibular.

E estou tendo dificuldades em digerir a resposta correta deste problema.Por que minha abordagem está incorreta?

Aqui está minha abordagem:
A parte de divisão da classificação por mesclagem divide recursivamente a lista de strings em sublistas com metade do número de strings cada.

Em seguida, a parte de mesclagem pega listas classificadas de dois de seus nós filhos e as mescla em sua própria lista classificada.Essa fusão se propaga para cima em direção à raiz e a lista inteira é eventualmente classificada.

A fusão funciona assim:
As duas listas infantis juntas têm $(n1+n2) = O(n)$ cordas.E para comparar duas strings como parte da fusão, precisamos comparar no máximo $n$ posições (já que as strings têm comprimento $n$).

Então a fusão leva $ eta(n*n) = eta(n^2)$

Agora a equação de recorrência se parece com: $T(n)= 2T(n/2) + eta(n^2)$

Usando o método mestre $n^{log_22}=n$
E $f(n)= heta(n^2)=\Omega(n^{log_22})$

Qual é o caso 3 do método Master.então $T(n)= eta(f(n))= eta(n^2)$ deve ser a resposta correta.

Answer 1

O erro e a correção

$$T(n)= 2T(n/2) + heta(n^2)$$

Como você pretendia, $T(n)$ é o pior momento do mergesorting $n$ cordas de comprimento $n$.Então, $T(n/2)$ no RHS significa o pior momento do mergesorting $n/2$ cordas de comprimento $n/2$.Portanto, durante o mergesort, o comprimento das strings diminui de $n$ para $n/2$!

O que deveria ter sido feito é usar uma variável diferente para expressar o número de strings no início de cada mergesort.Vamos definir $T(m,n)$ ser o custo do mergesorting $m$ cordas de comprimento $n$.Agora, teremos

$$T(m, n)= 2T(m/2, n) + heta(mn),$$

do qual podemos deduzir $$T(m,n) = heta(nm\log m).$$

---

Outra abordagem correta

Mesclar tipo de $n$ itens levam $ eta(n\log n)$ tempo, assumindo um custo unitário de comparação.Na verdade, o mergesort usa $ eta(n\log n)$ comparações.Agora que custa $ eta(n)$ para comparar duas strings de comprimento $n$ na pior hora, a pior hora da fusão $n$ cordas de comprimento $n$ deveria estar $ eta(n\cdot n\log n)$.