Divisão e conquista

Para ordenar [8,3,6,1], podemos ordenar [8,3] e [6,1] separadamente e fundir as respostas ordenadas. A divisão e conquista resolve subproblemas menores por recursão e combina as soluções parciais numa solução completa.

A prova tem duas obrigações: mostrar que a divisão cobre todos os casos do problema inteiro e que a combinação reconstrói a resposta a partir das partes. O custo conta as chamadas recursivas, o tamanho de cada uma e o trabalho feito fora delas. Dividir a entrada não garante por si só um algoritmo rápido, como mostra Hanoi no fim da lição.

Merge sort

Divide um vetor em duas metades, ordena cada uma e funde os dois vetores ordenados. Na fusão, compara os primeiros elementos ainda não usados e retira o menor. Quando um lado acaba, acrescenta o restante do outro.

Na fusão de [3,8] com [1,6], escolhemos 1, depois 3, depois 6 e finalmente 8. Antes de cada escolha, a saída já contém os menores elementos retirados em ordem, e os próximos candidatos são os menores ainda disponíveis de cada lado, por isso retirar o menor mantém o invariante. Por indução no tamanho, as metades estão ordenadas e a fusão ordena o vetor inteiro.

Escolher primeiro o elemento da metade esquerda em empate preserva a ordem original dos elementos iguais, tornando o algoritmo estável. Trocar essa regra não altera a ordenação por valor, mas pode perder estabilidade.

Para $n$ potência de dois,

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

No nível $j$ há $2^j$ subproblemas de tamanho $n/2^j$, com trabalho total $\Theta(n)$. Há $\log_2 n$ níveis até às folhas, logo $T(n)=\Theta(n\log n)$. Arredondar tamanhos não muda a ordem. A implementação habitual usa $O(n)$ espaço auxiliar para fusão e $O(\log n)$ para chamadas.

Teorema mestre

O formato é $T(n)=aT(n/b)+f(n)$, com $a\ge1$, $b>1$ constantes e um caso base de custo constante. Compara $f(n)$ com $n^{\log_b a}$, o custo associado às folhas.

Condição	Resultado
$f(n)=O(n^{\log_b a-\varepsilon})$ para algum $\varepsilon>0$	$\Theta(n^{\log_b a})$
$f(n)=\Theta(n^{\log_b a})$	$\Theta(n^{\log_b a}\log n)$
$f(n)=\Omega(n^{\log_b a+\varepsilon})$ e $af(n/b)\le cf(n)$ para algum $c<1$, a partir de certo tamanho	$\Theta(f(n))$

A diferença polinomial nos casos 1 e 3 e a condição de regularidade do caso 3 fazem parte do enunciado. Não concluas só pelo sinal de uma comparação informal.

Em $T(n)=4T(n/2)+n$, temos $n^{\log_2 4}=n^2$ e aplica-se o primeiro caso: $\Theta(n^2)$. Com trabalho $n^2$, dá $\Theta(n^2\log n)$; com trabalho $n^3$, dá $\Theta(n^3)$ e a regularidade verifica-se porque $4(n/2)^3=n^3/2$.

Há extensões para $f(n)=\Theta(n^{\log_b a}\log^k n)$, mas as três linhas acima não resolvem qualquer função. Uma recorrência como $T(n)=T(n-1)+n$ não tem subproblemas de tamanho $n/b$. Usa expansão ou soma: $T(n)=\Theta(1+2+\cdots+n)=\Theta(n^2)$.

Subvetor que atravessa o meio

Para um intervalo contíguo não vazio de soma máxima, divide entre os índices $m$ e $m+1$. A resposta está totalmente à esquerda, totalmente à direita ou atravessa a divisão.

O terceiro caso é a soma do melhor sufixo da esquerda com o melhor prefixo da direita. Percorre da divisão para fora, acumulando somas e guardando os melhores extremos. Qualquer intervalo que atravessa contém esses dois pedaços, portanto escolher os melhores independentemente maximiza o cruzamento.

No vetor [-4,3,-1,5,-6,2], divide depois do $-1$. Na esquerda, o melhor intervalo é [3], soma 3; na direita é [5], soma 5. O melhor sufixo da esquerda é [3,-1], soma 2. O melhor prefixo da direita é [5], soma 5. O cruzamento soma 7 e vence.

No caso base de um elemento, devolve o próprio elemento. Inicializar sufixos ou prefixos a zero admite uma parte vazia e pode falsear a variante não vazia com valores negativos.

A procura do cruzamento custa $\Theta(n)$, dando $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$. Podemos devolver com cada subproblema a soma total, melhor prefixo, melhor sufixo e melhor intervalo. Com estes quatro resumos, a combinação custa $\Theta(1)$ e a recorrência passa a $2T(n/2)+\Theta(1)=\Theta(n)$. Isso exige mudar a informação devolvida, não apenas retirar o ciclo da combinação.

Exponenciação por quadrados

Para inteiro $k\ge0$, calcular $a^k$ por multiplicações sucessivas exige $k-1$ multiplicações quando $k>0$. Usamos

$$a^{2r}=(a^r)^2,\qquad a^{2r+1}=a(a^r)^2,\qquad a^0=1.$$

Calcula $a^r$ uma vez e guarda-o. Para $3^{13}$, obtemos $3^1=3$, $3^3=3\cdot3^2=27$, $3^6=27^2=729$ e $3^{13}=3\cdot729^2=1594323$. A recorrência é $T(k)=T(\lfloor k/2\rfloor)+\Theta(1)$ e o número de multiplicações é $O(\log(k+1))$.

Chamar a mesma função duas vezes para as duas parcelas do quadrado daria $2T(k/2)+\Theta(1)$ e desperdiçaria o resultado. Se os inteiros tiverem precisão arbitrária, o custo de cada multiplicação cresce com o número de bits. O limite logarítmico conta multiplicações, não afirma tempo logarítmico em bits para produzir um número com muitos dígitos.

Pico de vetor estritamente unimodal

Um vetor é estritamente unimodal quando cresce de forma estrita até um pico e depois decresce de forma estrita. Com $[1,3,5,4,2]$, o pico é $5$ no índice $2$. Só esta hipótese permite descartar metade por comparação local.

Compara $A[m]$ com $A[m+1]$ no meio. Se $A[m]<A[m+1]$, o pico está à direita; se $A[m]>A[m+1]$, está à esquerda ou é $m$. A igualdade nunca acontece no caso estrito. Cada passo reduz o intervalo a cerca de metade, com trabalho $O(1)$ fora da chamada, logo $T(n)=T(n/2)+O(1)=O(\log n)$.

Usando índices de 0 a 4 e $m=\lfloor(lo+hi)/2\rfloor$, começamos com $m=2$. Como $A[2]=5>A[3]=4$, conservamos os índices 0 a 2. Agora $m=1$ e $3<5$, pelo que conservamos apenas o índice 2. O pico é 5.

Com repetições, comparar dois valores iguais pode esconder um pico dos dois lados. Em $[1,3,1,1,1,1,1]$ e $[1,1,1,1,1,3,1]$, os índices 3 e 4 contêm 1 em ambos os vetores, mas o pico está em lados opostos. Em geral, um vetor de valores 1 com uma única ocorrência de 3 é fracamente unimodal, seja qual for a posição do 3. Valores iguais não localizam esse pico; no pior caso é preciso examinar $\Theta(n)$ posições. A Questão 7 do primeiro mini-teste (Spring 2026) pede o algoritmo $O(\log n)$ no caso estrito e pergunta pelo caso fraco com repetições.

Torres de Hanoi

Os discos começam empilhados por tamanho, com o maior em baixo. Só podemos mover o disco do topo, um de cada vez, e nunca colocar um maior sobre um menor. Para mover $n$ discos da haste $A$ para $C$, usando $B$, precisamos de mover primeiro os $n-1$ pequenos para $B$, mover o maior de $A$ para $C$ e mover os pequenos de $B$ para $C$.

O caso $n=0$ não faz movimentos. A recorrência para o número de movimentos é

$$H(n)=2H(n-1)+1,\quad H(0)=0,$$

com solução $H(n)=2^n-1$. Por indução, se $H(n-1)=2^{n-1}-1$, então $H(n)=2(2^{n-1}-1)+1=2^n-1$.

Este número também é um limite inferior: antes de mover o maior, todos os pequenos têm de sair da sua haste e do destino; depois têm de regressar ao destino. As duas fases exigem pelo menos $H(n-1)$ movimentos cada. O algoritmo atinge esse mínimo.

Não aplica o teorema mestre, pois o tamanho diminui por 1. Divisão e conquista é uma técnica de desenho, não uma garantia de custo polinomial: gerar a sequência custa $\Theta(2^n)$, embora a pilha tenha apenas profundidade $n$.