Modelo de divisão e conquista
Extraia do ordenamento por intercalação o modelo de três etapas — dividir, conquistar e combinar — e aplique-o sistematicamente a novos formatos de problema.
Modelo de divisão e conquista é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é Divisão e Conquista?
Divisão e Conquista (D&C) resolve um problema dividindo-o em subproblemas independentes do mesmo tipo, resolvendo cada um recursivamente e combinando suas soluções. A palavra-chave é independente — os subproblemas não compartilham estado (ao contrário de DP, em que há sobreposição). Exemplos clássicos: ordenação por intercalação, busca binária, ordenação rápida, par de pontos mais próximo e multiplicação rápida de matrizes. A D&C normalmente alcança tempo O(n log n) por meio do modelo de três etapas.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]O Modelo de Três Etapas
Todo algoritmo de D&C segue três etapas: (1) Dividir — divida o problema em dois (ou mais) subproblemas menores, normalmente no ponto médio. (2) Conquistar — resolva cada subproblema recursivamente. Defina um caso-base para interromper a recursão (geralmente n ≤ 1). (3) Combinar — mescle ou combine as soluções dos subproblemas na solução geral. A criatividade está inteiramente na etapa Combinar; Dividir geralmente consiste apenas em separar no ponto médio.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)Ordenação por Intercalação como Exemplo Canônico
A ordenação por intercalação ilustra perfeitamente a D&C: Divida o vetor no ponto médio. Conquiste ordenando recursivamente cada metade. Combine intercalando as duas metades ordenadas em O(n). É na etapa de intercalação que todo o trabalho acontece. Recorrência: T(n) = 2T(n/2) + O(n). Pelo Teorema Mestre, caso 2: T(n) = O(n log n). Esta é a recorrência de D&C mais importante para memorizar.
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]Referência Rápida do Teorema Mestre
O Teorema Mestre resolve recorrências da forma T(n) = aT(n/b) + f(n): Caso 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Caso 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Caso 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Ordenação por intercalação: a=2, b=2, f(n)=O(n), n^log_2(2)=n → Caso 2 → O(n log n).
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)Subvetor de Soma Máxima: Abordagem de D&C
Na abordagem de D&C para o subvetor de soma máxima, a resposta está inteiramente na metade esquerda, inteiramente na metade direita ou atravessa o ponto médio. No caso que atravessa o ponto médio, avance para a esquerda a partir do meio e para a direita a partir de mid+1, obtendo a soma máxima em cada direção, e então combine os resultados. Essa abordagem de D&C em O(n log n) é mais lenta que a de Kadane, em O(n), mas demonstra o modelo de forma excelente e é uma pergunta comum em entrevistas sobre D&C.
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6Função de Potência: Exponenciação Rápida
Potência Rápida (LeetCode 50): calcule x^n em O(log n) usando D&C. Se n for par: x^n = (x^(n/2))^2. Se n for ímpar: x^n = x × x^(n-1). Trate n negativo com x^(-n) = 1/x^n. Cada chamada recursiva reduz n pela metade, portanto a profundidade é O(log n). Este é um exemplo claro em que a etapa Combinar consiste apenas em uma multiplicação — simples, mas eficaz.
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1Vetor Ordenado para BST
Converter Vetor Ordenado em BST (LeetCode 108) usa D&C: escolha o ponto médio como raiz (garantindo o equilíbrio da altura), construa recursivamente a subárvore esquerda a partir da metade esquerda e a subárvore direita a partir da metade direita. Isso produz uma BST balanceada em altura com altura mínima O(log n). A estrutura de D&C é semelhante à busca binária — cada nível da recursão atribui o ponto médio como raiz do subintervalo atual.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)Quando D&C Não é a Melhor Escolha
A D&C tem sobrecarga: profundidade da pilha de chamadas de função, divisão do vetor em fatias (se não forem usados índices) e a etapa de combinação. Ela é ideal quando a etapa de combinação tem custo O(n) ou menor. Quando os subproblemas se sobrepõem, a D&C recalcula soluções desnecessariamente — é necessário usar DP. Quando a etapa de combinação domina (por exemplo, O(n²)), a D&C não melhora as abordagens ingênuas. Saiba quando escolher cada uma: D&C para subproblemas independentes e DP para subproblemas sobrepostos.
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!D&C para Busca Binária em Matriz Ordenada
A busca em uma matriz 2D (LeetCode 240), na qual cada linha e cada coluna estão ordenadas, pode ser resolvida com D&C: comece pelo canto superior direito. Se o valor atual > o alvo, mova-se para a esquerda (elimina a coluna). Se o valor atual < o alvo, mova-se para baixo (elimina a linha). Se forem iguais, o alvo foi encontrado. Esse algoritmo O(m+n) tecnicamente não é uma D&C recursiva, mas compartilha a ideia principal: eliminar metade do espaço de busca a cada etapa.
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # FalseAnálise da Árvore de Recursão
Para recorrências de D&C que não se encaixam no Teorema Mestre, use o método da árvore de recursão. Desenhe cada nível das chamadas recursivas e some o trabalho de cada nível. Ordenação por intercalação: no nível k, há 2^k subproblemas de tamanho n/2^k. Trabalho por nível = 2^k × O(n/2^k) = O(n). O número total de níveis = log n. Trabalho total = O(n log n). Esse método visual funciona para qualquer recorrência e ajuda a desenvolver a intuição de por que a D&C geralmente alcança O(n log n).
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')Comunicação em Entrevistas sobre D&C
Ao apresentar uma solução de D&C em uma entrevista: (1) declare explicitamente as três etapas: 'Vou dividir no ponto médio, resolver recursivamente cada metade e então combinar por meio da intercalação.' (2) Identifique claramente o caso-base. (3) Derive a recorrência: T(n) = 2T(n/2) + O(n). (4) Aplique o Teorema Mestre ou a árvore de recursão para derivar O(n log n). (5) Mencione quando a D&C é melhor ou pior que as alternativas (DP para subproblemas sobrepostos, algoritmo de Kadane para subvetor de soma máxima).
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: Divisão e Conquista segue o modelo: caso-base → divisão no ponto médio → conquista recursiva → combinação, T(n) = 2T(n/2) + O(n) resulta em O(n log n) pelo Caso 2 do Teorema Mestre e a D&C é ideal para subproblemas independentes, enquanto DP é necessária quando os subproblemas se sobrepõem. A seguir, aplicaremos D&C para contar inversões em um vetor usando uma ordenação por intercalação modificada.
Perguntas Frequentes
A aula “Modelo de divisão e conquista” é grátis?
Sim — o texto completo de “Modelo de divisão e conquista” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Modelo de divisão e conquista”?
Extraia do ordenamento por intercalação o modelo de três etapas — dividir, conquistar e combinar — e aplique-o sistematicamente a novos formatos de problema. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Modelo de divisão e conquista”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Modelo de divisão e conquista
- Contar inversões usando ordenamento por intercalação modificado
- Elemento majoritário: votação de Boyer-Moore
- Mediana de dois vetores ordenados