View
111
Download
4
Category
Preview:
Citation preview
Aula 13
Lembra...
• F(n)=F(n/2)+3 com F(1)=5• Obrigamos n a ser potência de 2, geralmente
isso não agrada muito, pois os valores de n ficam muito restritos.
• Podemos melhorar isso, mas vai ajudar em algo?
Sejamos mais precisos...
• um método é executado com n/2 arredondado ou para cima ou para baixo.
• F(n)=F(n/2)+3 com F(1)=5 (verm)• F(n)=F(n/2)+3 com F(1)=5 (az)
• Qual a diferença entre essas recorrências precisamente computadas e 3*lg2(n)+5 (pt)?
f(n)=3*log(n)+5 p/n>1
0 200 400 600 800 1000
510
15
20
25
30
35
n
f
Lembre que isso quer dizer tempo de execução ou quantidade de memória.
• ... então podemos nos contentar com um limitante (superior/inferior).
• Uma forma fácil de escrever esses limitantes é a notação O-grande!!!!
T(n) = 2 T(n/2) + 7n + 2
• Que tipo de algoritmo tem complexidade com esse tipo de recorrência?
• Lembra do anterior...• F(n)=F(n/2)+3 com F(1)=5• Sabemos que o tempo de execução da busca
binária tem essa recorrência e T(n)=O(lg(n))
... geralmente é difícil escrever uma recorrência!
• T(n) = 2 T(n/2) + 7n + 2 • ... como começar?• por similaridade, desconfio que seja: algo com
cara de n*log(n)...• ... precisamos determinar a solução exata??
Lembre de 2 slides atrás!!• ... um limitante é suficiente!
Proposição: T(n) ≤ 10n lg n p/n>2
T(n) = 2T(n/2) + 7n + 2 ≤ ≤ 2(10 n/2) lg(n/2) + 7n + 2 ≤ ≤ 20 (n/2) lg(n/2) + 7n + 2 == 10n (lg n − lg 2) + 7n + 2 == 10n lg n − 10n + 7n + 2 == 10n lg n − 3n + 2 ≤ ≤ 10n lg n .
Prova por indução
É sempre assim? Uma fórmula cai do céu e provamos por indução??
Existem outros jeitos de chegar ao limitante!
• T(n) = 2 T(n/2) + 7n + 2• F(n)=F(n/2)+3
Recommended