Question

（14）已知n次多项式,

    如果在一种算法中，计算（k＝2，3，4，…，n）的值需要k－1次乘法，计算的值共需要9次运算（6次乘法，3次加法），那么计算的值共需要               次运算．

下面给出一种减少运算次数的算法：

（k＝0， 1，2，…，n－1）．利用该算法，计算的值共需要6次运算，计算的值共需要        次运算．

Answer 1

（14）n(n＋3)；2n.

 

解析：P_n（x₀）=a₀x₀ⁿ+a₁x₀^n－1+…+a_n－1x₀+a₀，共需n次加法运算，每个小因式中所需乘法运算依

次为n，n－1，…，1，0.故总运算次数为n+n+（n－1）+…+1=n+=n（n+3）.

 

第二种算法中，P₀（x₀）=a₀不需要运算，P₁（x₀）=x₀P₀（x₀）+a₁，需2次运算，

 

P₂（x₀）=x₀P₁（x₀）+a₂需2+2次运算，依次往下，P_n（x₀）需2n次运算.