Upload
internet
View
111
Download
1
Embed Size (px)
Citation preview
UFES Berilhes B. Garcia
Dividir-e-Conquistar
Recursividade em estruturas– Divida o problema em vários sub-problemas
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.
UFES Berilhes B. Garcia
Um Exemplo: Merge Sort
Dividir: Divida a seqüência de n-elementos a ser ordenada em duas subsequências de n/2 elementos cada uma.
Conquistar: Ordene as duas subseqüências recursivamente utilizando o merge sort.
Combinar: Funda as duas subseqüências ordenadas de modo a produzir uma resposta ordenada.
UFES 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) se n = 1
T(n) = 2T(n/2) + (n) 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) se n c
T(n) = a T(n/b) + D(n) + C(n) caso contrário
UFES 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
c n + 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