100
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 08:20, 10 March 2016
, 08:20, 10 March 2016no edit summary
<math>h_{n} = \alpha 2 ^ {n - 1}</math>
para alguma constante <math>/alfa </math>. (A potência de 2 é N-1, em vez de N, porque a recorrência começa no 1 em vez de 0.) Soluções para a H são obtidos a partir das soluções para h por adição de uma solução particular para H. Agora, H tem a solução constante <math>H_ N} = {-1</math>, para todo n, então todas as soluções para a H são da forma
<math>H_ {n} = /alpha 2 ^ {n} - 1</math>
'''Figure''': file = ch05 / 3lines.eps
Neste caso, o número <math>R_ {3}</math> das regiões é 7, de modo que a estimativa inicial que<math> R_ {n}</math> é <math>n ^ {2}</math> não pode ser certa. Para encontrar <math>r_ {4}</math>, temos de acrescentar uma quarta linha para o diagrama. Isto sugere tentar calcular <math>r_ {4}</math> em termos de <math>r_ {3}</math>, para que possamos pensar em <math>\ {r_ {n} \} </math>como uma relação de recorrência. A figura mostra que a situação parece quando uma quarta linha é adicionada a três linhas existentes.
'''Figure''': file = ch05 / 4lines.eps
Vamos agora fazer a análise do algoritmo para ver como relações de recorrência "Divide and Conquer" são geradas. Em geral, uma relação de recorrência do tipo dividir e conquistar tem a forma
<math> {r_} {n r_n = a \cdot r_ {n / K} + b </math>
para algumas constantes a, K e b. Agora, a rotina Maple rSolve não tem absolutamente nenhuma dificuldade para lidar com até mesmo o tipo mais geral de relação dividir e conquistar.