（霍纳（hornor）规则的正确性）给定系数a0,a..._

（霍纳（hornor）规则的正确性）给定系数a₀,a₁,...,a_n和x的值，代码片段

1 y=0
2 for i=n downto 0
3      y=ai + x*y

实现了用于求多项式

$P(x)=\sum_{k=0}^{n}{a_{k}x^{k}}=a_{0}+x(a_{1}+x(a_{2}+...+x(a_{n-1}+xa_{n})...))$

的霍纳规则。

a.借助 $\Theta$ 记号，实现霍纳规则的以上代码片段的运行时间是多少？

b.编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？

c.考虑一下循环不变式：

在第2~3行for 循环每次迭代的开始有

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

把没有项的和式解释为等于0.遵循下面的循环不等式证明结构，使用该循环不等式来证明终止时有 $y=\sum_{k=0}^{n}{a_{k}x^{k}}$ 。

d.最后证明上面给出的代码片段将正确的求由系数a₀,a₁,...,a_n刻画的多项式的值。

（霍纳（hornor）规则的正确性）给定系数a0,a...