Dividir-e-Conquistar

UFES
Recursividade em estruturas
– Divida o problema em vários subproblemas menores que são similares
ao original, mas de tamanho menor
– Conquiste os sub-problemas,
resolvendo-os recursivamente. Se eles
são pequenos o bastante, então
resolvo-os de uma maneira direta.
– Combine as soluções para criar uma
solução para o problema original.
Berilhes B. Garcia
Um Exemplo: Merge Sort

Dividir: Divida a seqüência de nelementos a ser ordenada em duas
subsequências de n/2 elementos cada
uma.
 Conquistar: Ordene as duas
subseqüências recursivamente utilizando
o merge sort.

UFES
Combinar: Funda as duas subseqüências
ordenadas de modo a produzir uma
resposta ordenada.
Berilhes B. Garcia
Merge-Sort (A, p, r)
Entrada: uma seqüência de n números
armazenados em um vetor A
Saída: uma seqüência ordenada de n números
1. if p < r
2.
then q  [(p+r)/2]
3.
Merge-Sort (A, p, q)
4.
Merge-Sort (A, q+1, r)
5.
Merge (A, p, q, r)
UFES
Berilhes B. Garcia
Análise do Merge Sort

Dividir: computar o elemento do méio toma
 (1)
 Conquistar: resolver 2 sub-problemas toma
2T(n/2)
 Combinar: fundir n-elementos toma  (n)

Total:
T(n) =  (1)
T(n) = 2T(n/2) +  (n)
se n = 1
se n > 1
 T(n) =  (n lg n)
UFES
Berilhes B. Garcia
Relações de Recorrência

Recurrências
– Método da Substituição
– Método da Iteração
– Método Mestre

Surgem a partir da abordagem Dividir
e Conquistar
(exemplo. MERGE-SORT)
T(n) =  (1)
T(n) = a T(n/b) + D(n) + C(n)
UFES
se n  c
caso contrário
Berilhes B. Garcia
Método da Substituição

Adivinhando a forma das soluções, e
então utilizando indução matemática
para encontrar as constantes e
mostrar que a solução está correta.

Este funciona bem quando é fácil
adivinhar. Mas, não há nenhuma
maneira gerak de adivinhar a solução
correta.
UFES
Berilhes B. Garcia
Um Exemplo

Resolver:
T(n) = 3T(n/3) + n
T(n)  3c n/3 lg n/3 + n
 c n lg (n/3) + n
= c n lg n - c n lg3 + n
= c n lg n - n (c lg 3 - 1)
 c n lg n
* O último passo é verdade para
c  1 / lg3.
UFES
Berilhes B. Garcia
Fazendo uma Boa Adivinhação

Adivinhando uma solução similar para uma
recorrência que você já tenha visto antes
– T(n) = 3T(n/3 + 5) + n similar à T(n) = 3T(n/3) + n
quando n é grande, a diferença entre n/3 e (n/3 + 5) é
insignificante.

Outra maneira é provar limites superior e inferior
para a recorrência e então reduzir o alcance da
incerteza.
– Comece com T(n) = (n) & T(n) = O(n2)  T(n) =  (n log n)
UFES
Berilhes B. Garcia
Sutilezas

Quando a prova matemática não pode ser
obtida por indução, tente ajustar sua
adivinhação com um termo de ordem mais
baixa. Por exemplo:
– Nós adivinhamos T(n)  O(n) para T(n) =
3T(n/3)+ 4, mas nós temos que
T(n)  3c n/3 + 4 = c n + 4
– Nova adicinhação é T(n)  c n - b, onde b  0
T(n)  3(c n/3 - b)+4 = c n - 3b + 4 = c n - b - (2b-4)
Portanto, T(n)  c n - b, se 2b - 4  0 ou se b  2
UFES
Berilhes B. Garcia
Mudança de Variáveis

Utilize manipulação algébrica para
transformar uma recorrência desconhecida
em uma similar que você já tenha visto.
– Considere T(n) = 2T(n1/2) + lg n
– Chame m = lg n e nós temos
T(2m) = 2T(2m/2) + m
– Ajust S(m) = T(2m) e nós temos
S(m) = 2S(m/2) + m  S(m) = O(m lg m)
– Mudando de volta de S(m) para T(n), nós temos
T(n) = T(2m) = S(m) = O(m lg m) = O(lg n lg lg n)
UFES
Berilhes B. Garcia
Evitando Armadilhas

Cuidado para não utilizar de forma inadequada.
Por exemplo:
– Nós podemos erroneamente provar T(n) = O(n)
adivinhando que T(n)  c n para T(n) = 2T(n/2) + n
T(n)  2c n/2 + n
 cn+n
= O(n)  Errado!
– O erro é que nós não provamos que T(n)  c n
UFES
Berilhes B. Garcia
Método da Iteração

Para expandir (iterar) a recorrência e expressa-lá
como uma somatória de termos dependentes
somente n e das condições iniciais.

Técnicas para avaliar somatórias podem ser
utilizadasd para fornecer os limites da solução.

A chave é focalizar-se sobre 2 parâmetros
– o número de vezes que a recorrência necessita ser
iterada para alcançar uma condição de fronteira
– A soma dos termos resultantes de cada nível do
processo de
UFES
Berilhes B. Garcia
Um Exemplo

Ressolver: T(n) = 3T(n/4) + n
T(n) = n + 3T(n/4)
= n + 3[n/4] + 9T(n/16)
= n + 3[n/4] + 9 [n/16] + 27T(n/64)
T(n)  n + 3n/4 + 9 n/16 + 27n/64 + … + 3log4 n (1)
 n  (3/4)i +  (nlog43)
= 4n+ o(n)
= O(n)
UFES
Berilhes B. Garcia
Árvores de Recursão

É uma maneira conveniente de visualizar o que ocorre
quando a recursão é iterada. Esta ajuda a organizar a
estrutura algébrica necessária para resolver a
recorrência. Para T(n) = 2T(n/2) + n2, nós temos
UFES
Berilhes B. Garcia
Árvores de Recursão
T(n) = (n2)
UFES
Berilhes B. Garcia
Árvores de Recursão

For T(n) = T(n/3) + T(2n/3) + n
T(n) = O(n lg n)
UFES
Berilhes B. Garcia
Método Mestre

Este fornece um método “livro de
receita” para a resolução de
recorrências da forma:
T(n) = a T(n/b) + f(n)
onde a  1 e b  1 são constantes e f(n) é uma
função assintoticamente positiva

A solução utilizando o método mestre
depende do teorema mestre (a seguir).
UFES
Berilhes B. Garcia
O Teorema Mestre
Assuma que a  1 e b > 1 são contantes, f(n) é função e T(n) está
definido para inteiros positivos por meio da recorrência
T(n) = a T(n/b) + f(n)
sendo n/b interpretado como n/b ou como n/b.
T(n) pode ser limitado assintoticamente como mostrado a
seguir:
1. Se f(n)=O(nlogba-) para alguma constante  > 0, então T(n)=
(nlogba).
2. Se f(n) = (nlogba), então T(n) = (nlogba lg n).
3. Se f(n) =  ( nlogba+ ) para alguma constante  > 0, e se
a f(n/b)  c f(n) para alguma constante c < 1 e n
suficientemente grande, então T(n)= (f(n)).
UFES
Berilhes B. Garcia
Teorema Mestre Simplicado
Assuma que a  1 e b > 1 são constantes e
T(n) é a recorrência
T(n) = a T(n/b) + c nk
definida para n  0.
1. Se a > bk, então T(n) = ( nlogba ).
2. Se a = bk, então T(n) = ( nk lg n ).
3. Se a < bk, então T(n) = ( nk ).
UFES
Berilhes B. Garcia
Exemplos

T(n) = 16T(n/4) + n
– a = 16, b=4, f(n) = n, assim nlogba = nlog416 = (n2)
– Desde que f(n) = O(nlog416 -  ) onde  = 1 
caso 1.
– Portanto, T(n) = (nlogba ) = (n2)

T(n) = T(3n/7) + 1
– a = 1, b=7/3, f(n) = 1, assim nlogba = nlog 7/3 1 = n0 = 1
– Desde que f(n) = O(nlogba)= (1),  caso 2.
– Portanto, T(n) = (nlogba lg n) = (lg n)
UFES
Berilhes B. Garcia
Exemplos (Cont.)

T(n) = 3T(n/4) + n lg n
– a = 3, b=4, f(n) = n lg n, nlogba = nlog43 = O(n0.793)
– Desde que f(n) = (nlog43 +  ) onde   0.2 
caso 3.
– Portanto, T(n) = (f(n)) = (n lg n)

T(n) = 2T(n/2) + n lg n
– a = 2, b=2, f(n) = n lg n, e nlogba = nlog22 = n
– f(n) é assintoticamente maior que nlogba, mas não
polinomialmente maior. A razão lg n é
assintoticamente menor que qualquer constante
positiva n. Logo, o Teorema Mestre não se
aplica.
UFES
Berilhes B. Garcia
Exercícios

Utilize o Método Mestre para resolver as
seguintes recorrências:
 T(n) = 4T(n/2) + n
 T(n) = 4T(n/2) + n2
 T(n) = 4T(n/2) + n3
UFES
Berilhes B. Garcia