问题

考虑下述算法(称为 Horner 法则)， 用于计算 $f(x)=\sum\limits_{i=0}^{n}a_i x^i$ 的值.

poly = 0;
for( i=n; i>=0; i--)
	poly = x * poly + a[i];

a) 对于多项式 $f(x)=4x^4+8x^3+x+2$, 求 $x=3$. 指出该算法的各步是如何进行的.

b) 解释该算法为什么能够解决这个问题.

c) 该算法的运行时间是多少?

请编写程序并完成上面的问题.

References:

Mark Allen Weiss 著, 张怀勇等译, 《数据结构与算法分析 C++ 描述》, 人民邮电出版社, 2012. 6. 【Exer 2.14】