已知多项式零点数组 如何以n log n复杂度计算其展开式系数

可以实现接近甚至达到你要求的n log n时间复杂度的转换，具体方案如下：

我们的目标是把给定零点数组a[0..n-1]对应的多项式 ∏(x - a[i]) 展开为幂次和的标准形式，你提到的朴素逐个乘一次式的方法时间复杂度为O(n²)，在n较大时开销确实很高。

常用可落地实现方案（复杂度O(n log²n)） #

这个方案实际运行效率非常接近O(n log n)，可以轻松处理n到10^5甚至更高规模的需求，实现逻辑如下：

• 分治拆分：将当前处理的零点数组平均拆为左右两个子数组
• 递归计算：分别递归展开两个子数组对应的多项式
• 快速乘法：使用FFT（浮点域）或NTT（模质数域）快速计算两个子多项式的乘积，得到当前区间对应的展开多项式

以你给出的示例为例：

x² - 1 = (x + 1)(x - 1)

对应的零点数组为[1, -1]，拆分后左数组对应多项式x - 1，右数组对应多项式x + 1，FFT相乘后直接得到标准形式的结果，和预期一致。

复杂度推导：递归总层数为log n，每一层所有多项式乘法的总运算量为O(n log n)，因此总复杂度为O(n log²n)，在绝大多数场景下已经足够使用。

严格O(n log n)的实现方案 #

如果你的运算场景是在支持N次原根的模数下（即做整数多项式运算模特定大质数），可以通过牛顿迭代结合多项式对数、指数运算的技巧实现严格O(n log n)的时间复杂度，但该方案实现难度较高，且适用范围有限，非特殊需求不需要使用。

注意事项 #

如果使用FFT实现快速乘法，要注意浮点精度误差的问题：如果最终系数是较大的整数，建议使用多模数NTT结合中国剩余定理合并结果，避免精度损失。

内容的提问来源于stack exchange，提问作者John