问一般多项式方程的慢速计算

EN

阿米亚：

代码运行缓慢的原因是计算不是多项式分解的，这意味着它没有利用运行的产品。例如，假设您的多项式是3次(即，y = a*x^3 + b*x^2 + c*x + d)。代码的设置方式使得x (类似于time变量)首先是立方体(3乘法+1乘以a)，然后是平方(2乘法+1乘以b)，然后引用(0乘法+1乘以c)，最后添加d。这相当于9次乘法和3次加法。用这种方法计算多项式需要sum(1:n)乘法和n加法。

相反，如果将多项式因式为：y = ((a*x + b)*x + c)*x + d，乘法次数将从9次降至3次，加法次数仍为3次。实际上，多项式因式分解方法使用n乘法和n加法计算多项式(n是多项式的阶数)。因此，人们可以看到，多项式因式分解在计算工作中的规模比我们称之为蛮力方法的速度要慢得多。

要对高次多项式执行此操作，我建议您将代码修改为：

N = length(time); %Get number of time values on which the polynomial evaluation is needed.
hmp = length(a); %I'm assuming a contains the polynomial coefficients in ascending order.
result = ones(N,1)*a(end); %Preallocate memory for results.
for i=hmp-1:-1:1
    result = result.*time + a(i); %Compute the factored parenthesis 'outward'
end

其中，N是要计算多项式的时间值的数量，hmp是最高的幅值幂。将result设为向量可使循环同时计算所有时间条目的多项式。这个for循环利用了多项式因式分解，这将比不必要地从头开始逐个元素计算幂的规模要小得多。