Análise de Algoritmos | Aulas | Dicionário | Índice

Ordenação: Mergesort

Esta página mostra como calcular o consumo de tempo do algoritmo de ordenação-por-intercalação conhecido como Mergesort. O algoritmo é recursivo, e portanto é preciso resolver uma recorrência para estimar seu consumo de tempo.

Esta página é inspirada na segunda parte do capítulo 2 do CLRS.

Ordenação por intercalação

Considere o clássico problema de ordenar um vetor A[1 .. n]. Nesta página, convém trocar o primeiro índice do vetor por uma variável e apresentar o problema assim:

Problema da ordenação:  Rearranjar um vetor A[p .. r] de modo que ele fique em ordem crescente.

O algoritmo Mergesort usa a estratégia da divisão e conquista para resolver o problema. O algoritmo recursivo resultante supõe que p ≤ r e adota o caso p = r como base da recursão:

Depois da linha 2, temos p ≤ q < r. Com isso, tanto A[p .. q] quanto A[q+1 .. r] são estritamente menores que A[p .. r]. Isso garante que a execução do algoritmo termina, mais cedo ou mais tarde.

O algoritmo Intercala recebe vetores crescentes A[p .. q] e A[q+1 .. r] e rearranja o vetor A[p .. q.. r] de modo que ele fique crescente. (Veja exercício no Apêndice). Para fazer isso, poderíamos ignorar o caráter ordenado dos dois subvetores e usar o algoritmo de inserção. Mas é possível fazer algo mais eficiente se tivermos permissão para usar um espaço de rascunho B[p .. r]:

Quanto tempo Intercala consome para processar um vetor com n = r − p + 1 elementos? Suponha, para simplificar, que cada execução de cada linha do código consome 1 unidade de tempo. Então a execução do algoritmo consumirá

6n + 5

unidades de tempo. (Se adotarmos um critério diferente de 1-unidade-de-tempo-por-linha, as contantes 6 e 5 podem mudar, mas o termo n certamente permanecerá.) Portanto, o consumo de tempo está em Θ(n) e o algoritmo é linear.

Desempenho do Mergesort

Seja n o número r−p+1 e  T(n)  o tempo que Mergesort consome para processar o vetor A[p .. r]. (O algoritmo não tem pior caso: todos os casos consomem essencialmente o mesmo tempo.) Suponha que cada execução das linhas 1 a 2 consome 1 unidade de tempo. A linha 5 consome 6n + 5 unidades de tempo, como vimos acima.

Portanto, o consumo de T(n) do algoritmo satisfaz a recorrência

para todo n > 1. Se adotarmos o valor inicial T(1) = 1, teremos a seguinte tabela para valores pequenos do argumento:

Como é possível extrair daí uma fórmula fechada para T(n)?

Solução da recorrência.  Se ficarmos só com os valores de n que são potências inteiras de 2, a recorrência se reduz a  T(n) = 2 T(n/2) + 6n + 7. Um cálculo semelhante ao que fizemos no exemplo D da página Recorrências mostra que  T(n) = 6 n lg n + 8n − 7  para n = 2, 4, 8, 16, etc. Esta fórmula só vale para potências inteiras de 2, mas deixa no ar a suspeita de que, para qualquer n, o tempo do Mergesort é Ο(n lg n). Poderíamos recorrer ao Teorema Mestre para confirmar a suspeita, mas prefiro verificar isso diretamente. Vou mostrar que

T(n)  ≤  16 n lg n

para n = 2, 3, 4, 5, 6, …  (A desigualdade não vale quando n = 1. Para determinar o fator 16, comecei fazendo os cálculos com c n lg n e acabei concluindo que 16 era um bom valor para c.)

Prova:  Quando n = 2, a desigualdade vale pois T(n) = T(2) = 21 < 32 = 16⋅2⋅1 = 16⋅2⋅lg 2 = 16 n lg n. Quando n = 3, a desigualdade vale pois T(n) = T(3) = 47 < 48 = 16⋅3 < 16⋅3⋅lg 3 = 16 n lg n. (Não é possível cuidar do caso n = 3 no passo da indução porque T(3) depende de T(1) e a hipótese de indução não pode ser aplicada a T(1).)

Suponha agora que n > 3 e que a desigualdade que queremos provar vale para argumentos de T menores que n. Então

Um dos passos da prova depende de saber que lg (2/3) < −0.5894. O último passo segue da desigualdade −2n + 7 ≤ 0, válida para n > 3. Isso termina a prova de que T(n) ≤ 16 n lg n para todo natural n ≥ 2.

É um ótimo exercício mostrar que existe um número positivo c tal que T(n) ≥ c n lg n para todo n suficientemente grande. Isso leva à conclusão de que

T(n) = Θ(n lg n) .

Portanto, o algoritmo Mergesort é linearítmico.

Se deixarmos de lado a hipótese artificial de que cada execução de cada linha simples do algoritmo, consome 1 unidade de tempo, a recorrência (*) pode ser escrita como  T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + Θ(n). A solução dessa recorrência, está em Θ(n lg n).