给定多项式的所有根，我必须想出一种算法，该算法可以比 O(n^2) 更快地生成系数。我无法解决这个问题。我很确定我应该使用快速傅立叶变换或傅立叶逆变换的概念，但我不知道如何修改输入使其不是单位的 n 次根。谁能指出我正确的方向？
最佳答案
这是一个 O(n * (log n)^2) 的解决方案:
基本情况:对于一个根 a，答案只是 x - a。
假设我们有一个包含多个根的列表。我们可以递归地解决列表的前半部分和后半部分的问题，然后使用快速傅里叶变换将结果相乘。
时间复杂度由等式 T(n) = 2 * T(n/2) + O(n log n) 得到，根据 Master 定理为 O(n * (log n)^2) .
关于algorithm - 给定所有根，如何在时间上比 O(n^2) 更快地找到多项式的系数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28465398/