Necessità di operazioni di convoluzione per il prodotto di due polinomi tramite metodo di forza bruta

Question

Riferimento: pagina 4 di questo documento

Dati due polinomi $ p (x) $ e $ q (x) $ ciascuno di grado $ n $ rappresentati in forma di coefficiente, prende $ mathcal { theta} (n) $ tempo per valutare dato alcuni input $ x $.

Nel riferimento collegato, al fine di ottenere il prodotto di questi due polinomi, $ c (x) = p (x) q (x) $, tramite forza bruta, dobbiamo calcolare nuovi coefficienti tramite convoluzione $ left (c_k = Sum_ {i = 0}^k a_i b_ {ki} destro) $ che prende $ mathcal { theta} (n^2) $ time.

Tuttavia, se volessimo valutare questo prodotto con un dato input $ x $, possiamo valutare i due polinomi $ p (x) $ e $ q (x) $ separatamente e quindi moltiplicare i due risultati scalari. Nel complesso, questo richiederebbe $ mathcal { theta} (n) $ tempo per due valutazioni e una moltiplicazione scalare. Questo ci consente di evitare di dover fare convoluzioni e sarebbe più veloce di $ mathcal { theta} (n^2) $.

Domanda: Quando si tratta di valutazione del prodotto di due polinomi, in realtà $ mathcal { theta} (n) $ usando il metodo sopra o siamo ancora condannati a $ mathcal { theta} (n^2) $?

Sono consapevole che c'è un modo più veloce per farlo in $ mathcal {o} (n log n) $ tempo tramite trasformata veloce di Fourier, ma sono più curioso della necessità dei calcoli della convoluzione. Sospetto che sia più se ci interessa di ottenere i coefficienti del prodotto rispetto alla valutazione effettiva, come in più ci preoccupiamo di conoscere $ {c_0, c_1, c_2, dotsc } $ di $ c (x) = p (x ) Q (x) $.