Divisão e conquista

O projeto de muitos algoritmos eficientes é baseado no método da divisão e conquista. Esse método (ou estratégia de projeto de algoritmos) consiste no seguinte:

Etapas

Dividir

Dividir o problema em uma ou mais subproblemas

Conquistar

Resolver os subproblemas caso esses sejam suficientemente pequenos, caso contrário continuar a divisão

Combinar

Soluções dos subproblemas para a solução do problema original

Vantagens

Eficiência do algoritmo
Tratamento da complexidade
Paralelismo
Acesso à memória

Processo

a instância dada do problema é dividida em duas ou mais instâncias menores,
cada instância menor é resolvida usando o próprio algoritmo que está sendo definido,
as soluções das instâncias menores são combinadas para produzir uma solução da instância original.

A segunda fase é implementada por uma chamada recursiva. Essa é a fase da conquista.

O método da divisão e conquista produz um algoritmo eficiente se a fase de divisão e a fase da combinação forem suficientemente rápidos.

algoritmo Altura

Um para o problema do segmento de soma máxima,

Busca binária:

divide a instância em duas menores e resolve uma delas; a fase de combinação é vazia.

Mergesort:

divide a instância em duas menores (essa fase é muito rápida) e resolve as duas instâncias menores; a fase de combinação é a que consome mais tempo.

Quicksort:

a fase da divisão é lenta e produz duas instâncias menores; a fase de combinação é muito rápida.

Algoritmo da mediana:

a fase da divisão, que produz duas instâncias menores, é lenta; a fase da conquista resolve uma dessas instâncias; a fase de combinação é muito rápida.

Algoritmo de Karatsuba:

a fase da divisão é muito rápida e produz três instâncias menores; a fase de combinação consiste em algumas operações aritméticas.

Par de pontos mais próximos:

Menor distancia entre 2 pontos.