算术算法

Question

我正在回答一些面试问题，偶然发现了这个问题。p(x) = a0 + a1x + a2x^2 + ... + anx^n。你可以使用什么算法来计算O(N^2)中p(x)的值？我完全不知道如何处理这个问题。

Answer 1

您可以通过直接求值或使用Horner's method在O(N)中执行此操作。各种操作的复杂性和涉及的方法的有用图表可以在这里找到：

Computational complexity of mathematical operations

霍纳的方法是一个串行过程，它优化了“在某些架构上使用本机乘法-累加指令进行求值的形式(A+ Bx)的子表达式”。一个更并行的版本是Estrin's scheme。

由于您可以在O(N)时间内计算p(x)，因此可以应用此方法N次来获得O(N^2) (如果这确实是您想要的...)。

Answer 2

由于每个项都是独立的，并且有N个项，因此必须执行多项式项的O(N)计算。由于最差的转换项是(a_n)*(x^n)，并且x^n可以用O(N)计算，因此您有足够的O(N^2)时间来实现算法。

但是，有一些技巧可以在O(N)时间内计算x^n，因此您可以做得更好:参见an implementation of pow()。此外，霍纳的方法，如其他答案所描述的那样，提供了一种快速的实现，即O(N)时间，因此也是O(N^2)时间。