Reduza uma medida real.
O tamanho precisa cair: número de itens, intervalo de índices, dígitos ou dimensão. Dividir conceitualmente não significa copiar dados; criar subarrays pode introduzir um custo que a análise precisa contar.
strategy / divide & conquer
próxima lente Divide and Conquer.
Reduzir um problema grande a partes menores, resolver e combinar com método.
visualização passo a passo
stage / DivideComo ordenar sem enfrentar tudo de uma vez?
901
302
703
104
805
206
foco atual / dividir o intervaloa faixa mostra o estado, não uma medição de tempo real
ação / progresso comparação / estado conflito / limite
telemetria / estratégia
passo01dividir o intervalo
camada0 → 1estado observado
códigolinha 3JavaScript
estadopausadocontrole manual
/ o que está acontecendodividir o intervalo
dividir o intervalo
combine com método.
O intervalo inteiro é grande demais para uma decisão única. O corte cria dois subproblemas menores.
→
princípio /
Subproblemas menores tornam a decisão tratável; a combinação reconstrói a resposta completa.
limite que não pode ser omitido
Dividir indiscriminadamente não garante eficiência. A relação entre tamanho, quantidade de subproblemas e custo da combinação define o resultado.
complexidade / mapa rápido
melhorO(n log n)
médioO(n log n)
piorO(n log n)
A visualização usa a recorrência T(n) = 2T(n/2) + O(n) para explicar o custo da ordenação por intercalação.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara o crescimento quando aumentam os itens, os estados possíveis ou as decisões de uma estratégia.
operações
O(n log n) · Itens em níveis
Todos os itens são tratados, mas as decisões são organizadas em níveis. O log₂(n) indica quantas divisões pela metade cabem até chegar a casos pequenos.
Dobrar n adiciona um nível de decisão; por isso o crescimento é maior que O(n), mas bem menor que uma comparação entre todos os pares.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para contrastar uma escolha local eficiente com o custo de preencher e reutilizar estados em problemas de capacidade. Greedy Algorithm e Dynamic Programming usam parâmetros diferentes: O(n·C) depende da capacidade C, e O(bᵈ) depende da ramificação b e da profundidade d. A régua contrasta modelos de crescimento; só compare a inclinação sob hipóteses explícitas sobre como esses parâmetros aumentam.
/ por baixo do palco
Um corte, uma combinação.
O destaque acompanha a decisão atual. Leia o pseudocódigo antes de trocar de linguagem; a implementação é uma tradução, não um novo algoritmo.
01se tamanho ≤ 1: retornar
02meio ← tamanho / 2
03esquerda ← resolver metade
04direita ← resolver metade
05retornar combinar(esquerda, direita)
implementação / JavaScript
01function mergeSort(items) { // Divide the input and combine sorted halves02 if (items.length <= 1) return items;03 const middle = Math.floor(items.length / 2);04 const left = mergeSort(items.slice(0, middle));05 const right = mergeSort(items.slice(middle));06 return merge(left, right);07}/ leitura técnica · arquitetura recursivaDividir não reduz
Dividir não reduz
o custo por si só.
Divide and Conquer resolve uma instância ao reduzi-la, resolver cada parte e combinar as respostas. A eficiência vem da forma completa dessa arquitetura: quantas chamadas surgem, quanto cada parte diminui e quanto trabalho a combinação adiciona em cada nível.
Pare em um caso-base correto.
Cada chamada deve trabalhar sobre uma instância menor da mesma família. O caso-base encerra a árvore e precisa devolver uma resposta correta antes que a indução recursiva possa começar.
Cobre o preço da reconstrução.
Mesclar listas, aplicar uma partição ou escolher uma resposta pode custar pouco, linearmente ou dominar o algoritmo. Combinar não é um detalhe posterior: é parte do contrato de custo.
recorrência / mapa do custo
T(n) = aT(n/b) + f(n)a conta quantas subchamadas nascem; b indica quanto o tamanho encolhe; e f(n) reúne divisão, combinação, cópias e partições feitas no nível atual. Mudar qualquer um desses termos pode mudar a classe assintótica.
/ leia a árvore, não apenas a chamadaProfundidade, ramificação
Profundidade, ramificação
e trabalho por nível.
Uma árvore balanceada costuma reduzir a altura para uma escala logarítmica. Uma árvore inclinada pode aproximar-se de uma cadeia de chamadas; QuickSort com pivôs muito ruins mostra por que “usar recursão” não garante desempenho.
MERGE SORT2 × n/2 + Θ(n)duas metades, mesclagem linear em cada nível; Θ(n log n).
BUSCA BINÁRIA1 × n/2 + Θ(1)uma metade continua; Θ(log n).
QUICKSORT BALANCEADO≈ 2 × n/2 + Θ(n)partição linear, caso típico Θ(n log n).
QUICKSORT DEGENERADO1 × (n − 1) + Θ(n)partições inclinadas; pior caso Θ(n²).
invariante / leitura da bancada
O recorte destacado representa uma instância menor, não trabalho “eliminado”. O custo só diminui quando os subproblemas progridem para o caso-base e a combinação evita refazer varreduras, cópias ou cálculos já produzidos em outros ramos.
/ fronteira importanteÁrvore de chamadas
Árvore de chamadas
ou grafo de estados?
Subproblemas disjuntos ou quase disjuntos favorecem Divide and Conquer. Se a mesma instância reaparece em vários ramos, uma recursão ingênua recalcula trabalho; memoização ou programação dinâmica pode registrar esse estado uma única vez.
PERGUNTADIVIDE AND CONQUERDYNAMIC PROGRAMMING
Subproblemasindependentes ou quase independentessobrepostos e reutilizáveis
Estruturaárvore de recursãografo ou tabela de estados
Risco centralcombinação cara ou divisão desequilibradaarmazenamento de muitos estados
ExemploMerge SortFibonacci com memoização
corretude / indução estrutural
Três elos para provar.
Base: a instância pequena está correta. Hipótese: cada chamada menor devolve uma solução correta. Passo: a combinação transforma essas soluções na resposta correta da instância atual. A mesma medida que diminui a entrada demonstra término; a combinação fecha a prova.
/ decisão de usoProjete a árvore
Projete a árvore
antes do código.
Use Divide and Conquer quando a entrada admite partes menores, a recursão não repete estados de modo relevante e a combinação preserva o ganho. Meça custos de cópia, memória auxiliar, profundidade da pilha e balanceamento. Se o particionamento for instável ou os subproblemas se sobrepuserem muito, escolha outra estratégia ou explique a proteção adotada.
fontes / para continuar