20302

题目

秦九韶算法是一种求解多项式的值的方法。

对于系数 $a_{0}, a_{1}, a_{2}, \dots, a_{n}$ ，多项式 $P (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{n} x^{n}$ 的值可以如下计算：

P (x) = ((a_{n} x + a_{n - 1}) x + \dots + a_{1}) x + a_{0}

(1) 写出秦九韶算法的时间复杂度。

(2) 如果依次计算多项式的每一项，最后求和，写出时间复杂度。

对于秦九韶算法，易得进行 n 次乘法和 n 次加法，故时间复杂度为 $O (n)$ 。

对于依次计算每一项，最后求和，计算第一项需要进行 0 次乘法，计算第二项需要进行 1 次乘法，以此类推，计算最后一项（第 n+1 项）需要进行 n 次乘法，总共进行 $\frac{n (n + 1)}{2}$ 次乘法，时间复杂度为 $O (n^{2})$ 。

(1) $O (n)$

(2) $O (n^{2})$