Resolvido: Algoritmos - Teoria e Prática - 3ª Ed. 2012 | Cap 30 Ex 4PA
50
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Nesse problema, dados os coeficientes tais que

Vamos mostrar como calcular para em tempo .

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

Perceba que ao substituirmos na expressão, todos os termos com expoentes não nulos são eliminados, de forma a termos . Além disso, ao derivarmos, um novo coeficiente igual ao grau da derivada é incluso no termo a ser calculado, de forma a termos a seguinte recorrência:

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Tendo um resultado, podemos, portanto, calcular o termo seguinte em tempo constante. Como teremos n resultados ao final do cálculo, conseguimos calcular todos eles em tempo .

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Concluímos, portanto, usando a fórmula de recorrência para a n-ésima derivada, que podemos calcular em tempo .

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Assine o PremiumCancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com 5.000 livros, escolha 5 por mês
  • check Videoaulas exclusivas
  • check Resumos por tópicos