Quel est l'algorithme le plus efficace pour calculer les coefficients polynomiaux à partir de ses racines?

Question

Donné $ n $ les racines, $ x_1, x_2, dotsc, x_n $, le polynôme monic correspondant est $ y = (x-x_1) (x-x_2) dotsm (x-x_n) = prod_ {i} ^ n (x - x_i) $. Pour obtenir les coefficients (c'est-à-dire $ y = sum_ {i} ^ n a_i x ^ i $), une expansion simple nécessite $ O (n ^ 2) $ pas.

Alternativement, si $ x_1, x_2, dotsc, x_n $ sont distincts les uns avec les autres. Le problème est équivalent à l'interpolation polynomiale avec $ n $ points: $ (x_1, 0), (x_2, 0), dotsc, (x_n, 0) $. L'algorithme d'interpolation polynomiale rapide peut être exécuté $ O (n log ^ 2 (n)) $ temps.

Je tiens à demander s'il y a mieux un algorithme plus efficace que $ O (n ^ 2) $? Même s'il y a des valeurs dupliquées parmi $ {x_i } $? Si cela aide, nous pouvons supposer que le polynôme est sur un champ fini principal, c'est-à-dire $ x_i in mathbf {f} _q $.