算术算法

Question

我正在经历一些面试问题，并偶然发现了这个问题。 p（x）= a0 + a1x + a2x^2 + ... + anx^n。你可以用什么算法来计算O（N^2）中p（x）的值？我对如何解决这个问题完全无能为力。

Answer 1

您可以在O(N)直接评估或Horner's method。用于各种操作的复杂性和所涉及的方法的有用的图表可以在这里找到：

Computational complexity of mathematical operations

Horner的方法是，优化形式（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()。另外Hoener的方法如其他答案所描述的那样提供了一个快速的实现，其时间是O(N)，因此也是O(N^2)时间。