2-3 Correctness of Horner's rule

The following code fragment implements Horner's rule for evaluating a polynomial

\[ \begin{aligned} P(x) & = \sum_{k = 0}^n a_k x^k \\\\ & = a_0 + x(a_1 + x (a_2 + \cdots + x(a_{n - 1} + x a_n) \cdots)), \end{aligned} \]

given the coefficients \(a_0, a_1, \ldots, a_n\) and a value of \(x\):

C++
1
2
3
y = 0
for i = n downto 0
    y = a[i] + x * y

a. In terms of \(\Theta\)-notation, what is the running time of this code fragment for Horner's rule?

b. Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner's rule

c. Consider the following loop invariant: At the start of each iteration of the for loop of lines 2-3,

\[y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k.\]

Interpret a summation with no terms as equaling \(0\). Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, \(y = \sum_{k = 0}^n a_k x^k\).

d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients \(a_0, a_1, \ldots, a_n\).

a. \(\Theta(n)\).

b.

C++
1
2
3
4
5
6
7
NAIVE-HORNER()
    y = 0
    for k = 0 to n
        temp = 1
        for i = 1 to k
            temp = temp * x
        y = y + a[k] * temp

The running time is \(\Theta(n^2)\), because of the nested loop. It is obviously slower.

c. Initialization: It is pretty trivial, since the summation has no terms which implies \(y = 0\).

Maintenance: By using the loop invariant, in the end of the \(i\)-th iteration, we have

\[ \begin{aligned} y & = a_i + x \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k \\\\ & = a_i x^0 + \sum_{k = 0}^{n - i - 1} a_{k + i + 1} x^{k + 1} \\\\ & = a_i x^0 + \sum_{k = 1}^{n - i} a_{k + i} x^k \\\\ & = \sum_{k = 0}^{n - i} a_{k + i} x^k. \end{aligned} \]

Termination: The loop terminates at \(i = -1\). If we substitute,

\[y = \sum_{k = 0}^{n - i - 1} a_{k + i + 1} x^k = \sum_{k = 0}^n a_k x^k.\]

d. The invariant of the loop is a sum that equals a polynomial with the given coefficients.

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