algorithm - 算术算法

Question

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

Answer 1

您可以O(N)通过直接评估或霍纳的方法来做到这一点。可以在此处找到有关各种操作的复杂性和所涉及方法的有用图表：

数学运算的计算复杂度

Horner 的方法是一个串行过程，用于优化“在某些体系结构上使用本机乘累加指令求值的形式 (A+Bx) 的子表达式”。一个更并行的版本是Estrin 的方案。

由于您可以计算p(x)时间O(N)，因此应用此方法N次数来实现O(N^2)（如果这确实是您所追求的......）。

Answer 2

由于每个项都是独立的并且有 N 个项，因此您必须执行O(N)多项式项的计算。由于最坏的演员是(a_n)*(x^n)并且x^n可以计算出来，因此O(N)您有确切O(N^2)的时间来实现算法的幼稚实现。

但是有一些技巧可以x^n在少于 O(N) 的时间内进行计算，因此您可以做得更好：请参阅pow() 的实现。此外，其他答案所描述的 Hoener 方法提供了一种快速实现，即O(N)时间，因此也是O(N^2)时间。