Embed Size (px)
Citation preview
Recorrências
Recorrências e Tempo de Execução
• Uma equação ou inequação que descreve uma função em termos
de seu valor sobre pequenas entradas
T(n) = T(n-1) + n
• Recorrências aparecem quando um algoritimo contém chamadas
recursivas para ele mesmo
• Qual é de fato o tempo de exeução de um algoritmo?
• É preciso resolver a recorrência
– Encontrar um fórmula explícita de uma expressão
– Limitar a recorrência por uma expressão que envolve n
Exemplos de Recorrências• T(n) = T(n-1) + n Θ(n2)
– Algoritmo recursivo que a cada loop examina a entrada e elimina um item
• T(n) = T(n/2) + c Θ(lgn)– Algoritmo recursivo que divide a entrada em cada passo
• T(n) = T(n/2) + n Θ(n)– Algoritmo recursivo que divide a entrada, mas precisa
examinar cada item na entrada• T(n) = 2T(n/2) + 1 Θ(n)
– Algoritmo recursivo que divide a entrada em duas metades e executa uma quantidade constante de operações
Algoritmos RecursivosBINARY-SEARCH
• Para um vetor ordenado A, verifique se x está no vetor A[lo…hi]
Alg.: BINARY-SEARCH (A, lo, hi, x)
if (lo > hi)return FALSE
mid (lo+hi)/2if x = A[mid]
return TRUEif ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)
12111097532
1 2 3 4 5 6 7 8
midlo hi
Exemplo• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
– lo = 1hi = 8 x = 7
mid = 4, lo = 5, hi = 8
mid = 6, A[mid] = x Encontrado!!!
119754321
119754321
1 2 3 4 5 6 7 8
Outro exemplo• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
– lo = 1 hi = 8 x = 6
mid = 4, lo = 5, hi = 8
mid = 6, A[6] = 7, lo = 5, hi = 5119754321
119754321
1 2 3 4 5 6 7 8
119754321 mid = 5, A[5] = 5, lo = 6, hi = 5 NÃO ENCONTRADO!
Análise do BINARY-SEARCH
Alg.: BINARY-SEARCH (A, lo, hi, x)if (lo > hi)
return FALSEmid (lo+hi)/2if x = A[mid]
return TRUEif ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)
• T(n) = c + T(n/2)
– T(n) – tempo de execução para um vetor de tamanho n
tempo contante: c2
mesmo problema de tamanho n/2mesmo problema de tamanho n/2
tempo contante: c1
tempo contante: c3
Métodos para resolver recorrências
• Iteração
• Substituição
• Árvore de Recursão
• Teorema Mestre
O Método da Iteração
• Converter a recorrência em um somatório e
tentar limitá-lo usando uma série conhecida
– Iterar a recorrência até a condição inicial ser
alcançada.
– Usar retro-substituição para expressar a
recorrência em termos de n e a condição inicial.
O Método da IteraçãoT(n) = c + T(n/2)
T(n) = c + T(n/2) = c + c + T(n/4) = c + c + c + T(n/8)
Assume n = 2k
T(n) = c + c + … + c + T(1)
= clgn + T(1) = Θ(lgn)
k times
T(n/2) = c + T(n/4)
T(n/4) = c + T(n/8)
Método da Iteração– ExemploT(n) = n + 2T(n/2)
T(n) = n + 2T(n/2) = n + 2(n/2 + 2T(n/4)) = n + n + 4T(n/4) = n + n + 4(n/4 + 2T(n/8)) = n + n + n + 8T(n/8)… = in + 2iT(n/2i) = kn + 2kT(1) = nlgn + nT(1) = Θ(nlgn)
Assume: n = 2k
T(n/2) = n/2 + 2T(n/4)
O método da substituição
1. Adivinhe uma solução
2. Use indução para provar que a solução está correta
Método da substituição
• Adivinhe uma solução (um chute)
– T(n) = O(g(n))
– Objetivo da indução: aplicar a definição de notação assintótica
• T(n) ≤ d g(n), para algum d > 0 e n ≥ n0
– Hipótese indutiva: T(k) ≤ d g(k) para todo k < n
• Prove a indução
– Use a hipótese indutiva para encontrar alguns valores de
constantes d e n0 para os quais a indução seja válida
Exemplo: Binary Search
T(n) = c + T(n/2)• Chute: T(n) = O(lgn)
– Indução: T(n) ≤ d lgn, para algum d e n ≥ n0
– Hipótese indutiva: T(n/2) ≤ d lg(n/2)
• Prova da indução:
T(n) = T(n/2) + c ≤ d lg(n/2) + c
= d lgn – d + c ≤ d lgn
se: – d + c ≤ 0, d ≥ c
• Caso base?
Exemplo 2
T(n) = T(n-1) + n
• Chute: T(n) = O(n2)
– Indução: T(n) ≤ c n2, para algum c e n ≥ n0
– Hipótese indutiva: T(n-1) ≤ c(n-1)2 para todo k < n
• Prova da indução:
T(n) = T(n-1) + n ≤ c (n-1)2 + n
= cn2 – (2cn – c - n) ≤ cn2
se: 2cn – c – n ≥ 0 c ≥ n/(2n-1) c ≥
1/(2 – 1/n)
– Para n ≥ 1 2 – 1/n ≥ 1 qualquer c ≥ 1 irá satisfazer
Exemplo 3
T(n) = 2T(n/2) + n• Chute: T(n) = O(nlgn)
– Indução: T(n) ≤ cn lgn, para algum c e n ≥ n0
– Hipótese indutiva : T(n/2) ≤ cn/2 lg(n/2)
• Prova da indução:
T(n) = 2T(n/2) + n ≤ 2c (n/2)lg(n/2) + n
= cn lgn – cn + n ≤ cn lgn
se: - cn + n ≤ 0 c ≥ 1
• Caso base?
Mudança de variáveis
– Fazendo: m = lgn n = 2m
T (2m) = 2T(2m/2) + m
– Tomando: S(m) = T(2m)
S(m) = 2S(m/2) + m S(m) = O(mlgm) (como visto
anteriormente)
T(n) = T(2m) = S(m) = O(mlgm)=O(lgnlglgn)
Idéia: transformar a recorrência em uma que seja
conhecida
T(n) = 2T( ) + lgn n
O método da árvore de recursão
Converter a recorrência em uma árvore:
– Cada nó representa o custo incorrido ´nos
vários níveis de recursão
– Some os custos de todos os níveis
Usado para “adivinhar” uma solução para a recorrência
Exemplo 1W(n) = 2W(n/2) + n2
• Tamanho do subproblema no nível i é: n/2i
• Tamanho de subproblema alcança 1 quando 1 = n/2i i = lgn• Custo de um problema no nível i = (n/2i)2 • Número de nós no nível i = 2i
• Custo total:
W(n) = O(n2)
22
0
21lg
0
2lg1lg
0
2
2)(
211
1)(
2
1
2
1)1(2
2)( nnOnnOnnnW
nnW
i
in
i
in
n
ii
Exemplo 2E.g.: T(n) = 3T(n/4) + cn2
• Tamanho do subproblema no nível i é: n/4i
• Tamanho do subproblema alcança 1quando 1 = n/4i i = log4n
• Custo de um nó no nível i = c(n/4i)2
• Número de nós no nível i = 3i último nível tem 3log4
n = nlog4
3 nós
• Custo total:
T(n) = O(n2)
)(
163
1
1
16
3
16
3)( 23log23log2
0
3log21log
0
444
4
nOncnncnncnnTi
iin
i
Exemplo 2 - Substituição
T(n) = 3T(n/4) + cn2
• Chute: T(n) = O(n2)
– Indução: T(n) ≤ dn2, para algum d e n ≥ n0
– Hipótese indutiva: T(n/4) ≤ d (n/4)2
• Prova da indução:
T(n) = 3T(n/4) + cn2
≤ 3d (n/4)2 + cn2
= (3/16) d n2 + cn2
≤ d n2 se: d ≥ (16/13)c
• Portanto: T(n) = O(n2)
Exemplo 3W(n) = W(n/3) +
W(2n/3) + n
• O maior caminho da raiz até uma
folha é:
n (2/3)n (2/3)2 n … 1
• Tamanho de subproblema alcança 1
quando
1 = (2/3)in i=log3/2n
• Custo de um problema no nível i = n
• Custo total:
W(n) = O(nlgn)
3 / 2
3 / 2
(log ) 1(log )
0
( ) ... 2 (1)n
n
i
W n n n n W
3 / 2
3 / 2
loglog 2
3/ 20
lg 11 log ( ) ( ) lg ( )
lg3 / 2 lg 3/ 2
n
i
nn n n n O n n O n n n O n
Example 3 - Substitution
W(n) = W(n/3) + W(2n/3) + O(n)• Chute: W(n) = O(nlgn)
– Indução: W(n) ≤ d nlgn, para algum d e n ≥ n0
– Hipótese indutiva: W(k) ≤ d klgk para qualquer K < n (n/3, 2n/3)
• Prova da indução:
Fica como exercício!
• T(n) = O(nlgn)
Teorema Mestre• “Receita de bolo” para resolver recorrências da forma:
onde, a ≥ 1, b > 1, e f(n) > 0
Idéia: comparar f(n) com nlogb
a
• f(n) é assintoticamente menor ou maior do que nlogb
a
por um fator polinomial n
• f(n) é assintoticamente igual a nlogb
a
)()( nfb
naTnT
Teorema Mestre
• “Receita de bolo” para resolver recorrências da forma:
onde, a ≥ 1, b > 1, e f(n) > 0
Caso 1: se f(n) = O(nlogba -) para algum > 0, então: T(n) = (nlog
ba)
Caso 2: se f(n) = (nlogb
a), então: T(n) = (nlogb
a lgn)
Caso 3: se f(n) = (nlogb
a +) para algum > 0, e se
af(n/b) ≤ cf(n) para algum c < 1 e todo n suficientemente grande,
então:
T(n) = (f(n))
)()( nfb
naTnT
Condição de regularidade
Exemplos
T(n) = 2T(n/2) + n
a = 2, b = 2, log22 = 1
Compare nlog2
2 com f(n) = n
f(n) = (n) Caso 2
T(n) = (nlgn)
Exemplos
T(n) = 2T(n/2) + n2
a = 2, b = 2, log22 = 1
Compare n com f(n) = n2
f(n) = (n1+) Caso 3 verificando a condição
de regularidade
a f(n/b) ≤ c f(n)
2 n2/4 ≤ c n2 c = ½ é uma solução (c<1)
T(n) = (n2)
Exemplos (cont.)
T(n) = 2T(n/2) +
a = 2, b = 2, log22 = 1
Compare n com f(n) = n1/2
f(n) = O(n1-) Caso 1
T(n) = (n)
n
Exemplos
T(n) = 3T(n/4) + nlgn
a = 3, b = 4, log43 = 0.793
Compare n0.793 com f(n) = nlgn
f(n) = (nlog4
3+) Case 3
Verificando a condição de regularidade:
3(n/4)lg(n/4) ≤ (3/4)nlgn = c f(n),
c=3/4
T(n) = (nlgn)
Árvore de Recursão
• Considere T(n)=3T(n/4)+cn2
T(n) cn2
T(n/4) T(n/4)T(n/4)
Árvore de Recursão
• Considere T(n)=3T(n/4)+cn2
T(n) cn2
c(n/4)2 c(n/4)2c(n/4)2
T(n/16) T(n/16) T(n/16)T(n/16) T(n/16) T(n/16)T(n/16) T(n/16) T(n/16)
Árvore de Recursão
• Considere T(n)=3T(n/4)+cn2
T(n) cn2
c(n/4)2 c(n/4)2c(n/4)2
c(n/16)2 c(n/16)2 c(n/16)2c(n/16)2 c(n/16)2 c(n/16)2c(n/16)2 c(n/16)2 c(n/16)2
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1)
log4n
nlog43
cn2
3cn2/16
32cn2/162
(n )log43
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
