Divisão e conquista

Merge e recorrência

Divide, ordena metades e funde com menores disponíveis. Estável se esquerda vence empates.

T(n)=2T(n/2)+\Theta(n),\quad T(1)=\Theta(1).

$\Theta(n\log n)$ por $\log_2 n$ níveis com $\Theta(n)$ cada. Fusão $O(n)$ auxiliar e $O(\log n)$ chamadas.

$T(n)=aT(n/b)+f(n)$ , com $a\ge1$ , $b>1$ e $\varepsilon>0$ . Compara $f$ com $n^{\log_b a$ :

Trabalho fora	Resultado
$O(n^{\log_b a-\varepsilon})$	$\Theta(n^{\log_b a})$
$\Theta(n^{\log_b a})$	$\Theta(n^{\log_b a}\log n)$
$\Omega(n^{\log_b a+\varepsilon})$ com $af(n/b)\le cf(n)$ para algum $c<1$ e $n$ grande	$\Theta(f(n))$

Diferença polinomial e regularidade fazem parte do teste. $T(n)=T(n-1)+n$ não cabe neste formato; soma direta dá $\Theta(n^2)$ .

Exemplos: $4T(n/2)+n$ dá $\Theta(n^2)$ ; com $n^2$ dá $\Theta(n^2\log n)$ ; com $n^3$ dá $\Theta(n^3)$ com regularidade $n^3/2$ .

Subvetor: divide em $m,m+1$ ; resposta à esquerda, à direita ou com sufixo esquerdo mais prefixo direito. Cruzamento $\Theta(n)$ dá $T=2T(n/2)+\Theta(n)$ . Com soma, prefixo, sufixo e melhor por nó, combinação $O(1)$ e $T=\Theta(n)$ .
Pico estrito: compara $A[m]$ com $A[m+1]$ ; descarta metade. $O(\log n)$ . Com repetições, pode exigir $\Theta(n)$ .
Potências: $a^{2r}=(a^r)^2$ , $a^{2r+1}=a(a^r)^2$ , $a^0=1$ . Calcula $a^r$ uma vez. $O(\log(k+1))$ multiplicações; custo em bits depende do tamanho.
Hanoi: $H(n)=2H(n-1)+1$ , $H(0)=0$ ; solução $2^n-1$ , também limite inferior. Fora do mestre; gerar sequência custa $\Theta(2^n)$ com pilha $O(n)$ .