Qual è l'algoritmo più efficiente per calcolare i coefficienti polinomiali dalle sue radici?

Question

Dato $ n $ radici, $ x_1, x_2, dotsc, x_n $, il polinomio monico corrispondente è $ y = (x-x_1) (x-x_2) dotsm (x-x_n) = prod_ {i}^n (x-x_i) $. Per ottenere i coefficienti (cioè $ y = sum_ {i}^n a_i x^i $), richiede una semplice espansione $ O (n^2) $ Passi.

In alternativa, se $ x_1, x_2, dotsc, x_n $ sono distinti tra loro. Il problema è equivalente all'interpolazione polinomiale con $ n $ punti: $ (x_1, 0), (x_2, 0), dotsc, (x_n, 0) $. L'algoritmo di interpolazione polinomiale veloce può essere eseguito $ O (n log^2 (n)) $ volta.

Voglio chiedere se esiste un algoritmo più efficiente di meglio di $ O (n^2) $? Anche se ci sono valori duplicati tra $ {x_i } $? Se aiuta, possiamo supporre che il polinomio sia su un campo finito primo, cioè $ x_i in mathbf {f} _q $.