Projeto e Análise de Algoritmos  
Aula 03 Técnicas de Projeto de Algoritmos  
(Divisão e Conquista)  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Estratégias de Projeto de Algoritmos  
Força Bruta (Brute Force)  
Dividir e Conquistar (Divide and Conquer)  
Diminuir e Conquistar (Decrease and Conquer)  
Transformar e Conquistar (Transform and Conquer)  
Compromisso TempoEspaço (Space and Time Tradeoffs)  
Estratégia Gulosa (Greedy)  
Programação Dinâmica (Dynamic Programming)  
Voltando Atrás (Backtracking)  
Ramificar e Limitar (Branch and Bound)  
Algoritmos Aproximados  
Divisão e Conquista  
Ideia geral:  
1
2
3
. Dividir a instância do problema em duas ou mais  
instâncias menores;  
. Resolver as instâncias menores (geralmente  
recursivamente);  
. Obter a solução para as instâncias originais (maiores)  
através da combinação destas soluções.  
Divisão e Conquista  
O paradigma de dividir e conquistar envolve 3 passos:  
Dividir  
Conquistar  
Combinar  
Divisão e Conquista  
Exemplo: calcular a soma de n números 0 + +1  
Se n > 1, podemos dividir o problema em duas  
instâncias do mesmo problema:  
Soma dos primeiros ꢂ/2 números;  
Soma dos ꢂ/2 números restantes;  
Uma vez estas duas somas computadas, adicionamos  
seus valores para obter o resultado final:  
0  
+ … + ꢀ1 = (0 + + ꢀ /1) + (0 + + ꢀ /1)  
Divisão e Conquista  
Esta é uma maneira eficiente de calcular a soma de n  
números?  
É mais eficiente do que uma adição força bruta?  
Nem todos os algoritmos baseados na técnica de  
dividir e conquistar são mais eficientes do que uma  
solução força bruta.  
Divisão e Conquista  
Em geral, o tempo gasto na execução das três etapas  
do algoritmo dividir e conquistar, é menor do que a  
resolução por outros métodos.  
A estratégia dividir e conquistar produz alguns dos  
algoritmos mais importantes e eficientes da área da  
computação.  
Importante: a estratégia dividir e conquistar pode ser  
facilmente adaptada a computação paralela.  
Exemplo 1: Multiplicação de Inteiros Grandes  
Problema: realizar a multiplicação de inteiros  
grandes (da ordem de 100 digitos decimais).  
Ex: 358712253797428009 × 153461234908764388 = ?  
Multiplicação Tradicional:  
Algoritmo de Força Bruta:  
-
-
multiplicação dígito a dígito;  
soma dígito a dígito;  
u
9
999  
___7__7_7__7_ v  
9993  
9993  
9993  
9993  
_
6
6
Complexidade: O(n2 + n) = O(n2)  
6
6
_
_____________  
7
7762223 u ×v  
Exemplo 1: Multiplicação de Inteiros Grandes  
Problema: realizar a multiplicação de inteiros  
grandes (da ordem de 100 digitos decimais).  
Outra forma de multiplicar números grandes?  
Passo 1 - Multiplicação dos Grandes  
A = x1 × y1 A = 12 × 56 = 672  
Passo 2 - Multiplicação dos Pequenos  
B = x2 × y2 B = 34 × 78 = 2652  
Passo 3 - Soma os dois grupos de x  
C = x1 + x2 C = 12 + 34 = 46  
Passo 4 - Soma os dois grupos de y  
D = y1 + y2 D = 56 + 78 = 134  
Passo 5 - Multiplique as somas dos grupos  
E = C × D E = 46 × 134 = 6164  
x1 x2  
x 12 34  
y
5
6 78  
y1 y2  
Exemplo 1: Multiplicação de Inteiros Grandes  
Problema: realizar a multiplicação de inteiros  
grandes (da ordem de 100 digitos decimais).  
Outra forma de multiplicar números grandes?  
Passo 6 - Subtraia o produto da soma dos dois grupos (E),  
o produto dos grandes (A) e o produto dos pequenos (B)  
x1 x2  
F = E - A - B  
F = 6164 - 672 - 2652 = 2840  
Passo 7 - Shift do produto dos grandes  
x 12 34  
G = A × ꢄꢅ 2  
m
2x2  
G = 672 × 10 = 6720000  
y
5
6 78  
Passo 8 - Shift do resultado das subtrações  
y1 y2  
H = F × ꢄꢅ m  
H = 2840 × 10 = 284000  
2
Passo 9 - Soma Final  
I = G + B + H I = 6720000 + 2652 + 284000  
Exemplo 1: Multiplicação de Inteiros Grandes  
Algoritmo de Karatsuba  
1
2
3
4
5
6
7
8
9
1
1
1
1
1
. KARATSUBA(u, v, n)  
. se n < 3 então  
. retorne u × v  
. senão  
O() = O(n1.585)  
. m ꢂ/2  
. a ꢆ/ꢄꢅꢇ  
. b u mod 10m  
. c ꢈ/ꢄꢅꢇ  
. d v mod 10m  
0. ac KARATSUBA(a, c, m)  
1. bd KARATSUBA(b, d, m)  
2. yKARATSUBA(a + b, c + d, m + 1)  
3. xac × 102m + (y - ac - bd)× 10m + bd  
4. retorne x  
Exemplo 1: Multiplicação de Inteiros Grandes  
Multiplicação Tradicional: O()  
Algoritmo de Karatsuba: O(3  
)
Wolfram Alpha:  
plot n^2 from n=0 to 15, n ^ log base 2 of 3 from n=0 to 15  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
ꢓꢔꢕꢖꢀꢂꢗꢔꢀ(ꢘ1, ꢙ1, ꢘ, ꢙ) = (ꢘ1ꢚꢘ) + (ꢙ1ꢚꢙ)  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
Divide…  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
Divide… Conquista...  
dE  
dD  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
Divide… Conquista... Combina!  
dE  
dED  
dD  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois deles  
que estão à distância mínima.  
Dividir: X[1 .. q], Y[1 .. q] (esquerda)  
X[q+1 .. n], Y [q+1 .. n] (direita)  
onde q := ꢂ/2  
Conquistar: Determine, recursivamente, a menor distância dE entre  
dois pontos da esquerda e a menor distância dD entre dois pontos da  
direita.  
Combinar: Devolva o mínimo entre dE, dD e a menor distância dED  
entre um ponto da esquerda e um ponto da direita.  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois deles  
que estão à distância mínima.  
Como realizar a função COMBINE de forma eficiente?  
COMBINE precisa considerar apenas pontos que estão a uma distância menor  
que d = min{dE, dD} da reta vertical.  
Problema: todos os pontos podem estar nessa faixa.  
Exemplo 2: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois deles  
que estão à distância mínima.  
Como realizar a função COMBINE de forma eficiente?  
Para cada ponto na faixa, olhamos apenas para pontos da faixa que tenham a  
coordenada Y no máximo d mais que este ponto.  
Em cada um dos dois quadrados de lado d, no máximo 4 pontos porque  
d ≤ dE e ddD. Logo não mais que 7 pontos assim (excluindo o ponto).  
Exemplo 2: Par de Pontos mais Próximos  
1
2
3
4
5
6
7
. PAR_MAIS_PROX(x, y, n)  
. para i 1 até n faça  
. px[i] i  
. py[i] i  
. MERGE-SORT(px, n, x)  
. MERGE-SORT(py, n, y)  
. retorne PAR_MAIS_PROX_REC(x, y, px, py, n)  
1
2
3
4
. PAR_MAIS_PROX_REC(x, y, px, py, n)  
. se n <= 3 então  
. retorna PAR_MAIS_PROX_FORCA_BRUTA(x, y, n)  
. senão  
, , , , , DIVIDE(x, y, px, py, n)  
5.  
6
. ie, je PAR_MAIS_PROX_REC(x, y, , , )  
7
. id, jd PAR_MAIS_PROX_REC(x, y, , ꢛ , )  
8
. retorna COMBINA(x, y, ie, je, id, jd, px, py, n)  
Exemplo 2: Par de Pontos mais Próximos  
1
2
3
4
. DIVIDE(x, y, px, py, n)  
. nen/2⌋  
. nd n − ne  
.
[1..ne] px[1..ne]  
5
6
7
8
9
1
1
1
.
[1..nd] px[ne+1..n]  
. xc x[px[ne]]  
. i 0  
. j 0  
. para k ← 1 até n faça  
0. se x[py[k]] <= xc então  
1.  
i i + 1  
[i] py[k]  
2.  
13. senão  
1
4.  
5.  
j ← j + 1  
[j] py[k]  
1
1
6. devolva , , ne, , , nd  
1
2
3
4
5
6
7
8
9
1
1
1
1
1
1
1
1
1
1
2
. COMBINA(x, y, ie, je, id, jd, px, py, n)  
min{DIST(x, y, ie, je),DIST(x, y, id, jd)}  
.
. xc x[px[n/2]]  
. m ꢡ  
.
t ← 0  
. para k ← 1 até n faça  
. se |x[py[k]] − xc| <= então  
.
.
t ← t + 1  
fy[t] ← py[k]  
0. para i 1 até t − 1 faça  
1. para ji + 1 até min{i + 7, t} faça  
2.  
3.  
4.  
5.  
6.  
d ← DIST(x, y, fy[i], fy[j])  
se d < m então  
m ← d  
p1 fy[i]  
p2 fy[j]  
7. se m = então  
8. retorne argmin{DIST(x,y,ie,je),DIST(x,y,id,jd)}  
9. senão  
0. retorne p1, p2  
Exemplo 2: Par de Pontos mais Próximos  
Análise da função DIVIDE:  
Linha 2-3  
Linha 4-5  
Linha 6-8  
Linha 9-15  
Linha 16  
O(1)  
O(n)  
O(1)  
O(n)  
O(1)  
Total → O(2n + 3) = O(n)  
Exemplo 2: Par de Pontos mais Próximos  
Análise da função COMBINA:  
Linha 2-5  
Linha 6-9  
Linha 10  
Linha 11-16 O(1)  
Linha 17-20 O(1)  
O(1)  
O(n)  
→ O(n)  
Total → O(2n + 3) = O(n)  
Exemplo 2: Par de Pontos mais Próximos  
1
2
3
4
5
6
7
. PAR_MAIS_PROX(x, y, n)  
. para i 1 até n faça  
. px[i] i  
O(n log n)  
. py[i] i  
. MERGE-SORT(px, n, x)  
. MERGE-SORT(py, n, y)  
. retorne PAR_MAIS_PROX_REC(x, y, px, py, n)  
. PAR_MAIS_PROX_REC(x, y, px, py, n)  
1
2
3
4
O(n log n)  
. se n <= 3 então  
. retorna PAR_MAIS_PROX_FORCA_BRUTA(x, y, n)  
. senão  
, , , , , DIVIDE(x, y, px, py, n)  
5.  
6
. ie, je PAR_MAIS_PROX_REC(x, y, , , )  
7
. id, jd PAR_MAIS_PROX_REC(x, y, , ꢛ , )  
8
. retorna COMBINA(x, y, ie, je, id, jd, px, py, n)  
Divisão e Conquista  
Outros algoritmos importantes baseados em divisão  
e conquista que veremos ao longo do curso:  
Merge Sort  
Quick Sort  
Quando Utilizar Divisão e Conquista?  
Existem três condições que indicam que a estratégia  
de divisão e conquista pode ser utilizada com  
sucesso:  
Deve ser possível decompor uma instância em sub-  
instâncias.  
A combinação dos resultados dever ser eficiente (trivial se  
possível).  
As sub-instâncias devem ser mais ou menos do mesmo  
tamanho.  
Comentários sobre a Divisão e Conquista  
Muitos algoritmos eficientes são baseados nesta  
técnica.  
Contudo, ela pode ser inaplicável e inferior a soluções  
algorítmicas mais simples.  
Outras estratégias semelhantes:  
Diminuir e Conquistar (Decrease and Conquer)  
Transformar e Conquistar (Transform and Conquer)  
Comentários sobre a Divisão e Conquista  
Vantagens:  
Pode gerar algoritmos eficientes com forte tendência a complexidade  
logarítmica;  
Facilmente paralelizável;  
Desvantagens:  
Geralmente são algoritmos recursivos (problema de estouro de pilha);  
Repetição de sub-problemas;  
Exercícios  
Lista de Exercícios 03 Divisão e Conquista  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Levitin. Introduction to the Design and  
Analysis of Algorithms, 3rd Edition, 2011.  
Capítulo 5: Divide-and-Conquer