0Pricing
DSA Interview Prep · Aula

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 DSA 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA 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))  # 6

Funçã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))    # 1

Vetor 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))  # False

Aná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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA 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 DSA 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 DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA 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 DSA Interview Prep?

Sim. Cada aula de DSA 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

  1. Modelo de divisão e conquista
  2. Contar inversões usando ordenamento por intercalação modificado
  3. Elemento majoritário: votação de Boyer-Moore
  4. Mediana de dois vetores ordenados
← Voltar para DSA Interview Prep