algorithm - Ruffini 规则算法的复杂性(大 O)是多少

Question

Ruffini's algorithm 的正确复杂性分析是什么？ ？

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，因此每次迭代后 last 的最大值将为 0，O(U ²), O(U³), O(U⁴), ..., O(U^{n+1 )。这意味着乘法将花费与 0、2 log U、3 log U、4 log U、...、n log U 成正比的时间。对所有乘法求和，这需要时间 O(n2 log U)，因此完成的总工作量为 O(n2 log U)。}