ex4-29-09

Prévia do material em texto

Bruno Brandao Borges, 2018014331. 
 
1) 
3 5 2 4 1 6 7 8 11 9 10 12 13 14 16 15 ​T(n) 
3 5 2 4 1 6 7 8 11 9 10 12 13 14 16 15 ​T(n/2) 
3 5 2 4 1 6 7 8 11 9 10 12 13 14 16 15 ​T(n/4) 
3 5 2 4 1 6 7 8 11 9 10 12 13 14 16 15 ​T(n/8) 
3 5 2 4 1 6 7 8 11 9 10 12 13 14 16 15 ​T(n/16) 
3 5 2 4 1 6 7 8 9 11 10 12 13 14 15 16 
2 3 4 5 1 6 7 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
Apesar de ser um algoritmo recursivo, que utiliza o metodo ​divide and 
conquer​, sua funcao de intercalacao possui tempo linear. Essa funcao eh 
chamada diversas vezes para a ‘combinacao’ dos vetores. Alem disso, 
numeros previamente comparados podem ser colocados sob teste outra(s) 
vez(es). Dessa forma, a tecnica de programacao dinamica nao eh capaz de 
acelerar o algoritmo especifico. 
2) 
a) Em A, temos uma funcao recursiva de recorrencia: 
T (m, n) = 2 se n = 0 ou m = n 
T (m, n) = 1 + T (m-1, n) + T (m-1,n-1) 
Temos uma resolucao exponecial dessa recorrencia, ​T (m, n) = O ([​13​6 ​]m−n+1​) 
Ja em B, observa-se uma aplicação de programação dinâmica, de ordem 
quadratica e sem repeticao. 
b) Por amarzenar os calculos em tabela e nao haver repeticao dos mesmos, 
observamos uma otimizacao na funcao B, sendo ela a mais eficiente.