Lançado · em melhoria
Algorithm
Divisão e conquista quebra um problema em subproblemas menores, resolve cada um recursivamente e combina os resultados, como no merge sort.
Divisão e conquista é uma técnica de projeto de algoritmos: o problema é quebrado em instâncias menores do mesmo problema (dividir), elas são resolvidas recursivamente (conquistar) e a resposta final é montada a partir dos resultados (combinar). Merge sort, busca binária, exponenciação rápida, quickselect, a multiplicação de Karatsuba e o par de pontos mais próximo seguem esse padrão.
Ela é importante porque muitas vezes transforma uma solução de força bruta O(n^2) em O(n log n) ou até O(log n). A ideia central de calcular na etapa de combinação a informação que cruza a divisão, como na contagem de inversões, aparece o tempo todo em entrevistas de programação, e as mesmas ideias estão por trás das bibliotecas de ordenação, da multiplicação de números grandes, da FFT e da exponenciação modular em criptografia.
Comece acompanhando o merge sort à mão para fixar dividir, conquistar e combinar e depois pratique montar recorrências como T(n) = aT(n/b) + f(n) e resolvê-las com o teorema mestre. Em seguida, implemente você mesmo a contagem de inversões, a exponenciação rápida e o quickselect, e aprenda a reconhecer quando subproblemas sobrepostos pedem programação dinâmica.
Dividir a entrada, resolver as partes recursivamente e combinar as respostas. Um caso base interrompe a recursão, e o custo da combinação costuma definir o tempo de execução.
O tempo é escrito como T(n) = aT(n/b) + f(n); comparar f(n) com n^(log_b a) dá resultados como O(n log n) para o merge sort.
Tratar em tempo linear os casos que envolvem as duas metades, como na contagem de inversões ou no subarray máximo, é a ideia central.
Quando sobra só um subproblema, como na busca binária, na exponenciação rápida e no quickselect, surgem algoritmos O(log n) ou O(n) esperado.
sort_count ordena a lista com merge sort e, sempre que um elemento da metade direita é escolhido primeiro, soma quantos elementos ainda esperam à esquerda; assim conta as inversões em O(n log n). power é a exponenciação rápida: divide o expoente pela metade e eleva ao quadrado, então precisa de apenas O(log e) multiplicações. Ao rodar python divide_and_conquer.py, o programa imprime a lista ordenada com suas 14 inversões e 3^200 módulo 1.000.000.007.
divide_and_conquer.py
def sort_count(a):
"""Return (sorted list, number of inversions) using merge sort."""
if len(a) <= 1:
return list(a), 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
merged, i, j, cross = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
cross += len(left) - i # right[j] is smaller than every left[i:]
merged += left[i:] + right[j:]
return merged, x + y + cross
def power(base, exp, mod):
"""base ** exp % mod with O(log exp) multiplications."""
if exp == 0:
return 1 % mod
half = power(base, exp // 2, mod)
result = half * half % mod
return result * base % mod if exp % 2 else result
if __name__ == "__main__":
print(sort_count([5, 2, 4, 7, 1, 3, 2, 6])) # ([1, 2, 2, 3, 4, 5, 6, 7], 14)
print(power(3, 200, 1_000_000_007)) # 136318165
python divide_and_conquer.pySeis capítulos que levam você da instalação aos conceitos essenciais de Divisão e conquista.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Divisão e conquista.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.