algorithm - 评估多项式系数的最佳复杂度

Question

我想找出根为 0,1,2...n-1 的 n 次多项式的系数。有人能推荐一个好的算法吗？我尝试使用 FFT，但速度不够快

标签： algorithmpolynomial-mathcoefficients

Answer 1

我将使用的简单解决方案是编写如下函数：

def poly_with_root_sequence (start, end, gap):
    if end < start + gap:
        return Polynomial([1, -start])
    else:
        p1 = poly_with_root_sequence(start, end, gap*2)
        p2 = poly_with_root_sequence(start+gap, end, gap*2)
        return p1 * p2

answer = poly_with_root_sequence(1, n, 1)

使用简单算法，这将进行O(n^2)算术运算。然而，一些操作将涉及非常大的数字。（请注意，大的数字n!不止n数字n。）但是我们已经安排了很少的操作将涉及非常大的数字。

除非您使用具有非常快速的乘法算法的多项式实现，否则仍然没有机会尽可能快地产生答案。

https://gist.github.com/ksenobojca/dc492206f8a8c7e9c75b155b5bd7a099宣传自己是 Python 中多项式相乘的 FFT 算法的实现。我无法验证。但它让你有机会走得相当快。