Solucao Exercicios aulas 05 e 06

Prévia do material em texto

Universidade Federal de Minas Gerais 
Departamento de Ciência da Computação 
Algoritmos e Estruturas de Dados II 
2º Semestre de 2011 
 
Solução dos Exercícios Aula 05 e 06.pdf 
 
1. 
 
 1 seg. 1 min. 1 hora 1 dia 1 mês 1 ano 1 século 
log n 2 1,1 x 1018 101.084 1026.009 10780.270 109.493.282 10949.328.194 
n 1 3,6 x 103 1,2 x 107 7,4 x 109 6,7 x 1012 9,9 x 1014 9,9 x 1018 
n 1 6 x 10 3,6 x 103 8,6 x 104 2,6 x 106 3,2 x 107 3,2 x 109 
n log n 1 15 414 6.787 150.687 1,5 x 106 1,2 x 108 
n2 1 7 60 293 1.609 5.615 56.156 
n3 1 3 15 44 137 315 1.466 
2n 0 5 11 16 21 24 31 
n! 1 4 6 8 9 10 12 
 
 
2. 
q: probabilidade pesquisa com sucesso 
1-q: probabilidade pesquisa sem sucesso 
 
Nas pesquisas com sucesso, cada registro tem a mesma probabilidade de ser acessado. 
pi: probabilidade de que o i-ésimo registro seja o procurado 
pi = q/n 
 
Número de comparações das pesquisas sem sucesso = n. Portanto, 
 
T(n) = 1 (q/n) + 2 (q/n) + 3 (q/n) + ... + n (q/n) + n (1-q) = ... = (2n+q-nq)/2 
 
 
3. 
a) Operação relevante é o número de vezes que a operação soma é realizada 
2
2
1
3...3)( nnT
i
n
ij
j
ik
===∑∑∑
= = =
 
 
b) 
Operação relevante é o número de comparações com os elementos do vetor 
Pior caso: 
∑
=
−+===
n
j
nnjnT
2
2
1
22
...)( 
Melhor caso: 
1...1)(
2
−===∑
=
nnT
n
j
 
Operação relevante é o número de movimentações com os elementos de A 
Pior caso: 
( )∑
=
−+==+=
n
j
nnjnT
2
2
3
2
5
2
...2)( 
Melhor caso: 
33...3
2
−==∑
=
n
n
j
 
 
c) 
Operação relevante é o número de comparações com os elementos do vetor 
∑∑
= +=
−===
n
i
n
ij
nn
nT
1 1
2
22
...1)( 
Operação relevante é o número de movimentações com os elementos do vetor. 
Pior caso: 
∑∑
= +=
−===
n
i
n
ii
nnnT
1
2
1 2
3
2
3
...3)( 
Melhor caso: 
T(n)=0 
 
d) 
Operação relevante é o número de comparações com a chave 
∑∑
−
= +=
−===
1
1 1
2
22
...1)(
n
i
n
ij
nn
nT 
Operação relevante é o número de movimentações com a chave 
∑
−
=
−===
1
1
)1(3...3)(
n
i
nnT 
 
4. 
Vamos tentar provar que 6n3 = Θ(n2). Para isso devemos achar constantes 01 >c , 02 >c e 00 >n , tal 
que: 
 
0
2
2
32
1 ;6 nnncnnc ≥∀≤≤ 
 
Dividindo por n2, temos: 
021 ;6 nncnc ≥∀≤≤ 
⇒≥⇒≤ nccn 66 22 Impossível, pois não existe constante que possa ser maior ou igual a 6n para todo n 
maior ou igual a 0n . 
 
Portanto, 6n3 ≠ Θ(n2)