Esta página é inspirada na segunda parte do capítulo 2 do CLRS. Ela trata do seguinte problema de ordenação:
Problema da ordenação: Rearranjar um vetor A[p..r] de modo que ele fique em ordem crescente.
Veja o verbete Merge sort na Wikipedia.
Podemos usar a estratégia da divisão e conquista para resolver o problema. O algoritmo resultante supõe que p ≤ r e adota o caso p = r como base da recursão:
| Mergesort (A, p, r) |
| 1 o se p < r então |
| 2 oooo q ← ⌊(p+r)/2⌋ |
| 3 oooo Mergesort (A, p, q) |
| 4 oooo Mergesort (A, q+1, r) |
| 5 oooo Intercala (A, p, q, r) |
(Veja definição de piso.) Observe que 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).
| p | q | q+1 | r | |||||||
| 111 | 333 | 555 | 555 | 777 | 999 | 999 | 222 | 444 | 666 | 888 |
O que faz o algoritmo Intercala? O algoritmo 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. Para resolver esse problema, eu poderia ignorar o caráter ordenado dos dois subvetores e usar o algoritmo de inserção. Mas é possível fazer algo mais eficiente (desde que tenhamos permissão para usar um vetor auxiliar B[p..r]):
| Intercala (A, p, q, r) |
| 16 o para i crescendo de p até q faça |
| 17 oooo B[i] ← A[i] |
| 18 o para j crescendo de q+1 até r faça |
| 19 oooo B[r+q+1−j] ← A[j] |
| 10 o i ← p |
| 11 o j ← r |
| 12 o para k crescendo de p até r faça |
| 13 oooo se B[i] ≤ B[j] |
| 14 ooooooo então A[k] ← B[i] |
| 15 ooooooo então i ← i+1 |
| 16 ooooooo senão A[k] ← B[j] |
| 17 ooooooo senão j ← j−1 |
(Esta versão do algoritmo é do Algorithms in C de Sedgewick.) Suponha que cada execução de cada linha do código consome 1 unidade de tempo. Então a execução de Intercala consome 6n+5 unidades de tempo, onde n é o número de elementos do vetor A[p..r].
Seja n o número r−p+1 e T(n) o tempo que Mergesort consome para processar um vetor A[p..r]. Suponha, para simplificar, que cada execução de cada linha do código (exceto as linhas 3 a 5) consome 1 unidade de tempo. Se levarmos em conta o consumo de Intercala, teremos T(1) = 1 e
| T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + 6n + 7 | (*) |
para todo n > 1. A figura explica essa recorrência:
| Mergesort (A, p, r) | ||
| 1 o se p < r então | 1 | |
| 2 oooo q ← ⌊(p+r)/2⌋ | 1 | |
| 3 oooo Mergesort (A, p, q) | T(⌈n/2⌉) | |
| 4 oooo Mergesort (A, q+1, r) | T(⌊n/2⌋) | |
| 5 oooo Intercala (A, p, q, r) | 6n+5 |
Eis alguns valores de T determinados pela recorrência:
| n | 1 | 2 | 3 | 4 |
| T(n) | 1 | 21 | 47 | 73 |
Como é possível extrair daí uma "fórmula fechada" para T(n) ?
Se ficarmos só com os valores de n que são potências inteiras de 2, nossa recorrência se reduz a T(n) = 2 T(n/2) + 6n + 7 . Um cálculo semelhante ao que fizemos na página Solução de recorrências mostra que T(n) = 6n 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 todo n, o tempo do Mergesort é Ο(n lg n). (Poderíamos recorrer ao "teorema mestre" para uma confirmação.) Para verificar esta suspeita, vamos mostrar que
T(n) ≤ 16 n lg n para n = 2, 3, 4, 5, 6, 7, …
(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 decidindo 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 = 16n lg n. Quando n = 3, a desigualdade vale pois T(n) = T(3) = 47 < 48 = 16×3 < 16×3×lg 3 = 16n 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
| T(n) | = | T(⌈n/2⌉) + T(⌊n/2⌋) + 6n + 7 |
| ≤ | 16 ⌈n/2⌉ lg ⌈n/2⌉ + 16 ⌊n/2⌋ lg ⌊n/2⌋ + 6n + 7 | |
| ≤ | 16 (⌈n/2⌉ + ⌊n/2⌋) lg ⌈n/2⌉ + 6n + 7 | |
| ≤ | 16 n lg ((n+1)/2) + 6n + 7 | |
| ≤ | 16 n lg (2n/3) + 6n + 7 | |
| = | 16 n (lg n + lg (2/3)) + 6n + 7 | |
| < | 16 n (lg n − 0.5) + 6n + 7 | |
| = | 16 n lg n − 8 n + 6n + 7 | |
| = | 16 n lg n − 2n + 7 | |
| ≤ | 16 n lg n . |
Um dos passos da prova usa a desigualdade (n+1)/2 ≤ 2n/3, que vale para todo n ≥ 3. O passo seguinte depende de saber que lg (2/3) < −0.5894. O último passo segue da desigualdade −2n+7 ≤ 0, válido para n > 3. Isso termina a prova de que T(n) ≤ 16 n lg n para todo natural n ≥ 2.
Se deixarmos de lado a hipótese artificial de que 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, tal como a solução de (*), está em Ο(n lg n). Portanto, o algoritmo Mergesort é do tipo ene-log-ene.