60
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