运行 霍纳方法的时间复杂度
Running time complexity of Horner's method
这是 Horner 计算 x 处多项式值的方法的伪代码（其中 a[i] 表示 x^i 的系数）：
y=a[0]
for i = n to 1
y = a[i] + x*y
网上很多文章都说霍纳法的运行时间与n成正比。
但是，由于 y 中的项数与 (n-i) 成正比（当我们已经完成 i 次迭代时），总时间不应该是 (n-1)+(n-2)....1 这是与 n^2 成正比？
还是我们总是认为任何乘法（无论项数如何）都需要常数时间？
您正在尝试计算多项式的 值 ，因此代码中的 y 是一个数字，而不是另一个多项式。您之前在某处定义了 x 到您希望计算多项式值的值。
是的，我们假设两个数的乘法是常量运算。所以在每次迭代中你做一个乘法和一个加法，两个整数之间的操作（可能是浮点数，取决于你操作的是什么字段）和一个赋值，所有这些都是常量。您执行这三个操作 n 次，总共产生 O(n).
此外，我认为您应该在第一步中将 a[n] 放入 y 并从 n-1 迭代到 0 或反转 for 循环的迭代，取决于您对多项式的表示。
这是 Horner 计算 x 处多项式值的方法的伪代码（其中 a[i] 表示 x^i 的系数）：
y=a[0]
for i = n to 1
y = a[i] + x*y
网上很多文章都说霍纳法的运行时间与n成正比。 但是，由于 y 中的项数与 (n-i) 成正比（当我们已经完成 i 次迭代时），总时间不应该是 (n-1)+(n-2)....1 这是与 n^2 成正比？ 还是我们总是认为任何乘法（无论项数如何）都需要常数时间？
您正在尝试计算多项式的 值 ，因此代码中的 y 是一个数字，而不是另一个多项式。您之前在某处定义了 x 到您希望计算多项式值的值。
是的，我们假设两个数的乘法是常量运算。所以在每次迭代中你做一个乘法和一个加法，两个整数之间的操作（可能是浮点数，取决于你操作的是什么字段）和一个赋值，所有这些都是常量。您执行这三个操作 n 次，总共产生 O(n).
此外，我认为您应该在第一步中将 a[n] 放入 y 并从 n-1 迭代到 0 或反转 for 循环的迭代，取决于您对多项式的表示。