# Divisão e conquista

Partir, resolver e combinar, com recorrências de custo resolvidas pela árvore de recursão.

Página: https://resumos.rgo.pt/cadeiras/da/divisao-conquista/

Divisão e conquista é a técnica dos três verbos: **divide** a entrada em partes, **conquista** cada parte recursivamente e **combina** as soluções parciais. A análise faz-se com recorrências, e a árvore de recursão transforma a recorrência numa conta de somar por níveis.

## Exemplo numérico: pesquisa binária

No vetor ordenado `[1, 3, 5, 7, 9, 11, 13]`, procurar o `11`. Compara com o meio (`7`, índice 3): `11` é maior, descarta a metade esquerda. Compara com o meio da metade direita (`11`, índice 5): encontrado. São **2 comparações** contra até 7 da procura linear. Cada passo corta a entrada a metade, por isso o custo é $O(\log n)$: a recorrência $T(n) = T(n/2) + O(1)$ soma $O(1)$ por cada um dos $\log n$ níveis. A condição escondida é o vetor estar ordenado; sem ela, a metade descartada podia conter o alvo.

```cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9, 11, 13};
    int alvo = 11, lo = 0, hi = 6;
    while (lo <= hi) {
        int m = (lo + hi) / 2;
        std::cout << "compara " << v[m] << "\n";
        if (v[m] == alvo) { std::cout << "encontrado\n"; break; }
        else if (v[m] < alvo) lo = m + 1;
        else hi = m - 1;
    }
}
```

## Exemplo com combinação: ordenação por fusão

Ordenar `[5, 2, 8, 1]`: divide em `[5, 2]` e `[8, 1]`; conquista recursivamente em `[2, 5]` e `[1, 8]`; combina fundindo as duas metades ordenadas, comparando cabeças: sai `1`, depois `2`, depois `5`, depois `8`. Resultado `[1, 2, 5, 8]`, com a fusão a custar $O(n)$. A recorrência $T(n) = 2T(n/2) + O(n)$ resolve-se pela árvore: há $\log n$ níveis (cada nível parte tudo a metade até chegar a singletons) e cada nível soma $O(n)$ de fusões. Total: **$O(n \log n)$**, melhor que qualquer ordenação por comparações consegue evitar no pior caso.

![Grafo da ordenação por fusão de 5, 2, 8 e 1: divide em 5, 2 e 8, 1; conquista em 2, 5 e 1, 8; combina em 1, 2, 5, 8.](https://resumos.rgo.pt/cadeiras/da/divisao-conquista/figura-1.svg)

Desenha a árvore

Perante uma recorrência, desenha dois ou três níveis com o custo de cada nó e soma por nível antes de tentares adivinhar a fórmula. Para $T(n) = 2T(n/2) + O(n)$ vês logo $\log n$ níveis de $O(n)$ cada. A árvore também mostra onde a recorrência vive: nas folhas (muito trabalho pequeno) ou na raiz (pouco trabalho grande).

![Árvore de recursão de T de n igual a 2T de n sobre 2 mais O de n: raiz n, dois filhos n sobre 2, quatro netos n sobre 4, com cada nível a somar n ao longo de log n níveis.](https://resumos.rgo.pt/cadeiras/da/divisao-conquista/figura-2.svg)

## A caixa do Teorema Mestre

A árvore funciona sempre, mas para recorrências da forma $T(n) = aT(n/b) + f(n)$ há um atalho com nome. Compara $f(n)$ com $n^{\log_b a}$:

*   Se $f$ cresce estritamente mais devagar, o trabalho está nas folhas: $T(n) = \Theta(n^{\log_b a})$.
*   Se $f$ empata com $n^{\log_b a}$, cada nível contribui igual: $T(n) = \Theta(n^{\log_b a} \log n)$.
*   Se $f$ cresce estritamente mais depressa (com uma condição de regularidade), a raiz manda: $T(n) = \Theta(f(n))$.

Aplica à fusão: $a = 2$, $b = 2$, $\log_2 2 = 1$ e $f(n) = \Theta(n)$, empate exato, logo $\Theta(n \log n)$, o mesmo que a árvore deu. Aplica à pesquisa binária: $a = 1$, $b = 2$, $\log_2 1 = 0$ e $f(n) = \Theta(1)$, empate outra vez, logo $\Theta(\log n)$. Usa o teorema para confirmar, mas mostra a árvore no teste: ela prova a conta em vez de citar o nome.

A mesma árvore serve para recorrências de outras páginas: o Fibonacci ingénuo da [programação dinâmica](https://resumos.rgo.pt/cadeiras/da/programacao-dinamica/) tem uma árvore exponencial, e é por isso que precisa de memoização. Se quiseres rever indução para provar estas contas, está em [indução e recorrência](https://resumos.rgo.pt/cadeiras/md/inducao-recorrencia/).

[Vídeo: Método da divisão e conquista e mergesort (PAA)](https://www.youtube.com/watch?v=ZmK4yi_RIgY)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=ZmK4yi_RIgY)

## Para saber mais

*   Notas sobre o mergesort com análise, de Paulo Feofiloff (IME-USP): [Mergesort](https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/mergsrt.html).