多项式求值时间复杂度

Question

我正在阅读这个链接：
http://www.geeksforgeeks.org/horners-method-polynomial-evaluation/

在这里，它说使用普通方法的时间复杂度是O(n^2)。但我想知道为什么？以下是我的分析：
假设我们有一个方程：2x^2 + x + 1
在这里，for循环将被执行3次，即(order+1)次。

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

根据这个问题，时间复杂度应该是O（n+1），即O（n）。为什么它说是O（n ^ 2）？我有点迷失了。即使有提示也行。

- Reckoner

Answer 1

虽然不太明显，但某些原始操作具有不同的时间复杂度。计算机在计算+运算结果时非常快，*较慢，%甚至更慢。这些操作在硬件上进行评估，因此它们需要恒定数量的处理器时钟周期。

但是，^操作并不简单。coefficient^i的复杂度不是O(1)/常数。计算结果的平凡方法是将coefficient乘以i次。这将在O(i)时间内完成。另一种方法是使用二进制指数方法，可以在更快的O(log(i))时间内完成。

为什么说它是O(n^2)？

多项式中有n个成员，您需要花费O(n)的时间来计算每个成员的指数运算结果。这就是为什么它是O(n²)的原因。

- Ivan Gritsenko

Answer 2

链接建议一种评估coefficient^i的天真方法是将coefficient乘以i次。 这是O（i）。 对于所有指数从0到n的重复操作将是O(n^2) 一个天真的方法来计算多项式是逐个计算所有项。 首先计算x^n，将该值与cn相乘，对其他术语重复相同步骤并返回总和。 如果我们使用简单的循环来评估x^n，则此方法的时间复杂度为O（n^2）。

它还声称，如果您使用更好的算法来计算coefficient^i，例如平方幂运算，其复杂度为O（log n），则总体复杂度将更低（O（n log n）），但Horner's方法甚至比这更好。

- Juan Lopes

---

根据我的看法，你是正确的。如果我们使用分治法来计算幂运算，那么其时间复杂度将为O(n)。因此，上述代码的总体复杂度将为O(n^2)。但是为什么这里说直接方法的复杂度也是O(n)呢？请查看此链接（代数函数部分）：https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations - Reckoner

Answer 3

是的，你说得对。你展示的这个形式通常被称为霍纳法则。它是线性的，因为基本操作（加法、乘法）的数量是O(n)，其中n是最高系数。

---

顺便提一下，你上面的代码似乎有一个错误。它可能应该是这样的：

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

（原始代码是一个无限循环）。否则，它可以被视为Horner的一种实现。

- Ami Tavory

---

那么我上面举的例子，就是真正的霍纳规则吗？ - Reckoner

@Reckoner 基本上是的，但你似乎有一个小错误。请看更新。 - Ami Tavory