30-4 Evaluating all derivatives of a polynomial at a point

Given a polynomial \(A(x)\) of degree-bound \(n\), we define its \(t\)th derivative by

\[ A^{(t)}(x) = \begin{cases} A(x) & \text{ if } t = 0, \\\\ \frac{d}{dx} A^{(t - 1)}(x) & \text{ if } 1 \le t \le n - 1, \\\\ 0 & \text{ if } t \ge n. \end{cases} \]

From the coefficient representation \((a_0, a_1, \dots, a_{n - 1})\) of \(A(x)\) and a given point \(x_0\), we wish to determine \(A^{(t)}(x_0)\) for \(t = 0, 1, \dots, n- 1\).

a. Given coefficients \(b_0, b_1, \dots, b_{n - 1}\) such that

\[A(x) = \sum_{j = 0}^{n - 1} b_j(x - x_0)^j,\]

show how to compute \(A^{(t)}(x_0)\) for \(t = 0, 1, \dots, n - 1\), in \(O(n)\) time.

b. Explain how to find \(b_0, b_1, \dots, b_{n - 1}\) in \(O(n\lg n)\) time, given \(A(x_0 + \omega_n^k)\) for \(k = 0, 1, \dots, n - 1\).

c. Prove that

\[A(x_0 + \omega_n^k) = \sum_{r = 0}^{n - 1} \Bigg(\frac{\omega_n^{kr}}{r!} \sum_{j = 0}^{n - 1} f(j)g(r - j)\Bigg),\]

where \(f(j) = a_j \cdot j!\) and

\[ g(l) = \begin{cases} x_0^{-l} / (-l)! & \text{ if } -(n - 1) \le l \le 0, \\\\ 0 & \text{ if } 1 \le l \le n - 1. \end{cases} \]

d. Explain how to evaluate \(A(x_0 + \omega_n^k)\) for \(k = 0, 1, \dots, n - 1\) in \(O(n\lg n)\) time. Conclude that we can evaluate all nontrivial derivatives of \(A(x)\) at \(x_0\) in \(O(n\lg n)\) time.

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用