Divis˜ao e Conquista Divis˜ao e Conquista

Divisão e Conquista
Fernando Lobo
Algoritmos e Estrutura de Dados II
1 / 27
Divisão e Conquista
I
É uma técnica para resolver problemas (veremos outras
técnicas mais adiante).
I
Consiste em 3 passos:
I
Dividir o problema em um ou mais subproblemas.
I
Conquistar (resolver) cada subproblema recursivamente.
I
Combinar os resultados dos subproblemas para a obter a
solução para o problema original.
2 / 27
Divisão e Conquista (cont.)
Tempo de execução é dado quase sempre por uma recorrência do
tipo: T (n) = D(n) + aT (n/b) + C (n).
I
D(n) é o tempo gasto a dividir o problema em subproblemas.
I
a é o número de subproblemas.
I
n/b é o tamanho de cada subproblema.
I
C (n) é o tempo gasto a combinar as soluções dos
subproblemas.
3 / 27
Divisão e Conquista (cont.)
I
Normalmente agregamos os tempos D(n) + C (n)
correspondentes ao tempo gasto pelo algoritmo em trabalho
não recursivo, chamando a esse tempo f (n).
I
Obtemos assim a recorrência T (n) = aT (n/b) + f (n), que é a
recorrência do Teorema Mestre.
4 / 27
Exemplo 1: MergeSort
T (n) = Θ(1) + 2T (n/2) + Θ(n)
= 2T (n/2) + Θ(n)
= Θ(n lg n)
5 / 27
Exemplo 2: QuickSort
I
Dividir: escolher o elemento pivot e dividir o array em 2
subarrays de tal forma que os elementos de um subarray sejam
menores que os elementos do outro subarray.
I
Conquistar: ordenar cada um dos subarrays recursivamente.
I
Combinar: não faz nada.
6 / 27
Exemplo 2: QuickSort (cont.)
I
Ao invés de MergeSort, aqui o tempo de divisão é Θ(n) e o
tempo de combinar é zero.
I
No melhor caso, o QuickSort divide sempre o array ao meio, e
o tempo de execução é dado por uma recorrência igual à do
MergeSort: T (n) = 2T (n/2) + Θ(n) = Θ(n lg n).
I
E no pior caso? O pior caso ocorre se o elemento pivot fosse
sempre o menor (ou o maior) elemento. Nesse caso a
recorrência seria dada por,
T (n) = T (n − 1) + T (1) + Θ(n)
= T (n − 1) + Θ(n)
= Θ(n2 )
7 / 27
Exemplo 2: QuickSort (cont.)
I
O pior caso é raro acontecer, especialmente se adoptarmos
uma boa estratégia para escolher o pivot.
I
Imaginemos que o QuickSort dividia sempre o array em 2
subarrays, um de tamanho n/10 e outro de tamanho 9n/10.
I
O tempo de execução seria dado por
T (n) = T (n/10) + T (9n/10) + Θ(n).
I
Não se pode aplicar o Teorema Mestre neste caso. Terı́amos
de provar usando o método de expansão da árvore de
recorrência.
I
Fica como exercı́cio para vocês fazerem. Vão ver que vai dar à
mesma Θ(n lg n).
8 / 27
Exemplo 3: Busca Binária
I
Dividir: verificar o elemento que está no meio de array.
I
Conquistar: resolve recursivamente o mesmo problema para
um dos subarrays (esq. ou dta.)
I
Combinar: não faz nada.
I
Recorrência é T (n) = T (n/2) + Θ(1).
I
Utilizando o Teorema Mestre, a = 1, b = 2, f (n) = c (em que
c é constante). nlogb a = nlog2 1 = n0 = 1 = Θ(f (n)). Estamos
no caso 2 do Teorema Mestre. A complexidade é
T (n) = Θ(lg n)
9 / 27
Exemplo 4: Potência de um número
I
Problema: calcular an , sendo n um número inteiro.
I
Algoritmo naive: |a ∗ a ∗ a{z∗ . . . ∗ a} = Θ(n).
n vezes
I
É possı́vel fazer melhor assimptoticamente?
10 / 27
Exemplo 4: Potência de um número (cont.)
I
Sim. Exemplo: 28 = 2 ∗ 2 ∗ 2 ∗ 2 ∗ 2 ∗ 2 ∗ 2 ∗ 2 = 256. Requer
7 multiplicações com o algoritmos naive.
I
Outro método:28 = (24 )2 = 162 = 256. Requer apenas
3 + 1 = 4 multiplicações.
I
No caso geral,
an =
I
an/2 ∗ an/2
, se n par
a(n−1)/2 ∗ a(n−1)/2 ∗ a , se n ı́mpar
Recorrência igual à da busca binária:
T (n) = T (n/2) + Θ(1) = Θ(lg n)
.
11 / 27
Exemplo 5: Multiplicação de inteiros
I
Faz sentido para inteiros muito grandes.
I
Solução óbvia: algoritmo da escola primária.
I
Exemplo:
23
* 12
-----46
+ 23
-----276
12 / 27
Exemplo 5: Multiplicação de inteiros (cont.)
I
Funciona em qualquer base. Seja x = 1100 e y = 1101,
ambos na base 2. xy = ?
1100
* 1101
-------1100
0000
1100
+ 1100
--------10011100
13 / 27
Exemplo 5: Multiplicação de inteiros (cont.)
I
Vamos assumir que ambos os números têm o mesmo no de
dı́gitos. Seja esse número n (n = 4 no exemplo anterior).
I
Tempo de execução do algoritmo em função de n: Θ(n2 ).
I
É possı́vel fazer melhor?
I
Sim, com divisão e conquista.
14 / 27
Exemplo 5: Divisão e Conquista (versão 1)
Ideia base:
I
Dividir x ao meio, ficando com x1 dı́gitos na parte esquerda
(os mais significativos) e x0 dı́gitos na parte direita (os menos
significativos). Fazer a mesma coisa para y .
I
x = x1 2n/2 + x0 . Do mesmo modo, y = y1 2n/2 + y0 .
xy
= (x1 2n/2 + x0 )(y1 2n/2 + y0 )
= x1 y1 2n + (x1 y0 + x0 y1 )2n/2 + x0 y0
15 / 27
Exemplo 5: Divisão e Conquista (versão 1)
I
As operações 2n e 2n/2 não requerem multiplicações.
Implementam-se com shifts.
I
Multiplicação de 2 números de n bits dá origem a 4
multiplicações de 2 números de n/2 bits + um no constante
de adições de números de n bits.
I
Ou seja, T (n) = 4T (n/2) + Θ(n).
I
Aplicando o Teorema Mestre: a = 4, b = 2.
nlogb a = nlog2 4 = n2
I
Estamos no caso 1: T (n) = Θ(n2 )
16 / 27
Exemplo 5: Divisão e Conquista (versão 1)
I
Conclusão: algoritmo de divisão e conquista não é melhor que
o algoritmo da escola primária. É apenas um algoritmo
complicado que tem a mesma complexidade!
17 / 27
Exemplo 5: Divisão e Conquista (versão 2)
I
Será possı́vel usar apenas 3 chamadas recursivas?
I
Se fosse possı́vel obterı́amos:
T (n) = 3T (n/2) + Θ(n) = Θ(nlog2 3 ) ≈ Θ(n1.59 )
I
Vamos ver que tal é possı́vel com um truque.
18 / 27
Exemplo 5: Divisão e Conquista (versão 2)
I
Queremos obter:
xy = x1 y1 2n + (x1 y0 + x0 y1 )2n/2 + x0 y0
I
Truque:
(x1 + x0 )(y1 + y0 ) = x1 y1 + x1 y0 + x0 y1 + x0 y0
I
Esta multiplicação tem as 4 multiplicações que pretendemos.
I
Se também calcularmos x1 y1 e x0 y0 recursivamente,
poderemos calcular xy com apenas 3 chamadas recursivas:
I
I
I
(x1 + x0 )(y1 + y0 )
x1 y1
x0 y0
// mult1
// mult2
// mult3
xy = x1 y1 2n + (mult1 − x1 y1 − x0 y0 )2n/2 + x0 y0
19 / 27
Exemplo 5: Pseudocódigo
Recursive-Multiply(x, y )
Dividir x ao meio e obter x1 e x0
Dividir y ao meio e obter y1 e y0
mult1 = Recursive-Multiply(x1 + x0 , y1 + y0 )
mult2 = Recursive-Multiply(x1 , y1 )
mult3 = Recursive-Multiply(x0 , y0 )
return mult2 ∗ 2n + (mult1 − mult2 − mult3) ∗ 2n/2 + mult3
20 / 27
Exemplo 6: Multiplicação de matrizes

A1,1 A1,2 · · ·
A2,1 A2,2 · · ·

 ..
..
..
 .
.
.
An,1 An,2 · · ·
 
A1,n
B1,1 B1,2 · · ·

A2,n 
 B2,1 B2,2 · · ·
..  ·  ..
..
..
.
.   .
.
An,n
Bn,1 Bn,2 · · ·
I
Input: Ai,j , Bi,j com i, j = 1, 2, . . . , n.
P
Output: Ci,j = A · B = nk=1 Ai,k · Bk,j
I
Ci,j é dado pelo produto da linha i pela coluna j.
I

B1,n
B2,n 

.. 
. 
Bn,n
21 / 27
Exemplo 6: Multiplicação de matrizes (cont.)
Algoritmo standard: 3 ciclos a varrer de 1 . . n.
Matrix-Multiply(A, B, C )
for i = 1 to n
for j = 1 to n
C [i, j] = 0
for k = 1 to n
C [i, j] = C [i, j] + A[i, k] ∗ B[k, j]
Complexidade: Θ(n3 ).
22 / 27
Exemplo 6: Divisão e Conquista (versão 1)
I
Ideia: dividir a matriz de n x n em 4 matrizes de
n
2
x n2 .
n
2
ea4
r s
a b
e f
=
·
t u
c d
g h
| {z } | {z } | {z }
C
A
B
r = ae + bg
s = af + bh
t = ce + dg
u = cf + dh
I
Dá origem a 8 multiplicações de matrizes de
somas de matrizes n2 x n2 .
n
2
x
23 / 27
Exemplo 6: Divisão e Conquista (versão 1)
I
Tempo de execução: T (n) = 8T (n/2) + Θ(n2 ).
I
Aplicando o Teorema Mestre: a = 8, b = 2.
nlogb a = nlog2 8 = n3
I
Estamos no caso 1: T (n) = Θ(n3 )
I
Conclusão: um algoritmo complicado que não é melhor que o
algoritmo standard.
24 / 27
Exemplo 6: versão 2, algoritmo de Strassen
Ideia: consegue reduzir de 8 para 7 no número de multiplicações!
I
Dá origem à recorrência: T (n) = 7T (n/2) + Θ(n2 ).
I
Aplicando o Teorema Mestre: T (n) = Θ(nlog2 7 ) ≈ Θ(n2.81 )
25 / 27
Exemplo 6: algoritmo de Strassen
P1
P2
P3
P4
P5
P6
P7
= a · (f − h)
= (a + b) · h
= (c + d) · e
= d · (g − e)
= (a + d) · (e + h)
= (b − d) · (g + h)
= (a − c) · (e + f )
7 mults, 18 somas
r = P5 + P4 − P2 + P6
s = P1 + P2
t = P3 + P4
u = P5 + P1 − P3 − P7
I
Verifiquem que é verdade. Não me perguntem como é que o
Sr. Strassen descobriu isto. Aparentemente ninguém sabe!
26 / 27
Verificação de r
r
= P5 + P4 − P2 + P6
= (a + d) · (e + h)
+ d · (g − e) − (a + b) · h
+ (b − d) · (g + h)
= ae + ah + de + dh + dg − de − ah − bh + bg + bh − dg − dh
= ae + bg
27 / 27