Ruffini 规则算法的复杂性（大 O）是多少
What's the complexity(Big O) of a Ruffini's rule algorithm
Ruffini's algorithm 的正确复杂性分析是什么？
我对鲁菲尼法则的理解是，它本质上是由这个伪代码给出的：
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) 的时间内完成，那么这个算法的 运行time 将是 O(n)，因为有循环的 n 次迭代每次执行 O(1) 工作。
在实践中，乘法比这需要更长的时间。具体来说，将两个分别为 a 和 b 位长的整数相乘通常需要时间 O(log a log b)，除非您使用 运行 比这快一点的专门算法。
所以我们假设每个系数和数字r最多都是U。在每次迭代中，我们乘以r并添加U，因此每次迭代后last的最大值将为0，O (U2), O(U3), O(U4), ... , O(Un+1)。这意味着乘法将花费与 0、2 log U、3 log U、4 log U、...、n log U 成正比的时间。对所有乘法求和，这需要时间 O(n2 log U), 所以完成的总工作量为 O(n2 log U).
Ruffini's algorithm 的正确复杂性分析是什么？
我对鲁菲尼法则的理解是，它本质上是由这个伪代码给出的：
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) 的时间内完成，那么这个算法的 运行time 将是 O(n)，因为有循环的 n 次迭代每次执行 O(1) 工作。
在实践中，乘法比这需要更长的时间。具体来说，将两个分别为 a 和 b 位长的整数相乘通常需要时间 O(log a log b)，除非您使用 运行 比这快一点的专门算法。
所以我们假设每个系数和数字r最多都是U。在每次迭代中，我们乘以r并添加U，因此每次迭代后last的最大值将为0，O (U2), O(U3), O(U4), ... , O(Un+1)。这意味着乘法将花费与 0、2 log U、3 log U、4 log U、...、n log U 成正比的时间。对所有乘法求和，这需要时间 O(n2 log U), 所以完成的总工作量为 O(n2 log U).