多项式评估时间复杂度

Question

我正在经历这个 link :
http://www.geeksforgeeks.org/horners-method-polynomial-evaluation/

这里说使用普通方法的时间复杂度是O(n^2)。但我想知道如何？这是我对此的分析：

假设我们有一个等式 like:2x^2 + x + 1
这里for循环会执行3次即(order+1)times

    for(int i = order ; i>=0 ; i++){
         result = result + (mat[i] * coefficient^i);
    }

所以根据这个，时间复杂度应该是 O(n+1) 即 O(n)。为什么说它是 O(n^2)？我有点迷茫 here.Even 一个提示就可以了。

Answer 1

link 表明计算 coefficient^i 的一种天真的方法是乘以 coefficient i 次。即 O(i)。对从 0 到 n 的所有指数重复此操作将是 O(n^2)

A naive way to evaluate a polynomial is to one by one evaluate all terms. First calculate x^n, multiply the value with cn, repeat the same steps for other terms and return the sum. Time complexity of this approach is O(n^2) if we use a simple loop for evaluation of x^n.

它还声称，如果你使用更好的算法来计算 coefficient^i，比如说，通过平方求幂，复杂度为 O(log n)，它的总复杂度会更低（O(n log n)), 但霍纳的方法会比那更好。

Answer 2

是的，你是对的。您显示的表格通常称为 Horner's Method。它是线性的，因为基本运算（加法、乘法）的数量是 O(n)，其中 n 是最高系数。

顺便说一句，您上面的代码似乎包含错误。应该是

for(int i = order ; i>=0 ; i--){

（原来是死循环）。否则，它可以被认为是Horner的实现。

Answer 3

嗯，它可能不是那么明显，但一些原始操作具有不同的时间复杂度。计算机在计算 + 操作的结果时非常快，* - 较慢，% - 甚至更慢。这些操作在硬件上进行评估，因此它们需要恒定数量的处理器滴答。

但是^操作没那么简单。 coefficient^i 复杂度不是 O(1)/常数。计算结果的简单方法是乘以 coefficient i 次。这将在 O(i) 时间内完成。另一种方法是使用二进制取幂方法，该方法提供更快的 O(log(i)) 时间。

Why does it say that its O(n^2)?

你的多项式有n个成员，你花O(n)的时间来计算每个成员的幂运算结果。这就是为什么它是 O(n²).

多项式评估时间复杂度

polynomial evaluation time complexity

algorithm

time-complexity

polynomials