我不知道理论的复杂性。但是，对于作为有限幂级数给出的多项式的所有零点，实际上最快的算法是 Traub [1] 的算法。它影响程度$n$多项式通常$O(n^2)$时间。

另见[2]。

对于仅通过其函数值可访问的多项式的因式分解，请参见例如我的论文 [3]。

参考：

1. 詹金斯 MA，特劳布 JF。1972. 算法 419：复多项式的零点 [C2]。ACM 15 的通讯：97-99。
2. 潘薇。1997. 求解多项式方程：一些历史和最新进展。暹罗评论 39：187。
3. 纽迈尔A. 2003. 封闭多项式的零簇。计算与应用数学杂志 156：389-401。[ PDF ]

正如 [1] 中提到的，Reif [2] 给出了一个$O(n \log^2 n (\log n + \log \epsilon))$当所有根都是实数的情况下的算法，即$O(n \log^3 n)$只要$\epsilon = n^{O(1)}$. 他只分析了精确算术的情况，但经过算法后，我相信它是（或可以修改为）向后稳定的。他的方法是专门针对实线的分裂圆方法的改进变体。

在精确的算术情况下，这给出$O(n \log^3 n)$Hermitian 三对角特征问题的算法。然而，由于第一步是计算特征多项式，我相信这种方法的稳定性会很差。

他指出，至少到 1999 年，对于一般复杂根案例的类似有效算法是未知的。

1. 为什么 Householder 反射不能对角化矩阵？
2. Reif, J. 1999。实根和对称三对角特征值问题的有效算法。