Ruffini规则算法的复杂性(Big O)是多少？

Question

Ruffini算法的正确复杂性分析是什么？

Answer 1

我对鲁菲尼规则的理解是，它本质上是由以下伪代码给出的：

let b = [];
let last = 0;

for (i from n - 1 to 0) {
    b.add(last + a[n]);
    last = (last + a[n]) * r;
}
let s = last;

如果我们假设所有系数都是整数，并且每次乘法都可以在 O(1) 时间内完成，那么该算法的运行时间将为 O(n)，因为循环的 n 次迭代执行 O(1)每个工作。

实际上，乘法需要比这更长的时间。具体来说，将两个分别为 a 和 b 位长的整数相乘通常需要花费 O(log a log b) 时间，除非您使用运行速度比这快一点的专用算法。

因此，我们假设每个系数和数字 r 都至多为 U。在每次迭代中，我们乘以 r 并添加 U，因此每次迭代后的最后一个最大值将为 0，O(U ² )， O(U ³ ), O(U ⁴ ), ..., O(U ⁿ⁺¹ )。这意味着乘法所花费的时间与 0, 2 log U, 3 log U, 4 log U, ..., n log U 成正比。将乘法相加，需要的时间为 O(n ² log U)，因此完成的总工作量为 O(n ² log U)。