Nécessité des opérations de convolution pour le produit de deux polynômes via une méthode de force brute

Question

Référence: page 4 de ceci document

Étant donné deux polynômes $ p (x) $ et $ q (x) $ chacun de degré $ n $ représenté sous forme de coefficient, il faut $ mathcal { theta} (n) $ le temps d'évaluer compte tenu de la contribution $ x $.

Dans la référence liée, afin d'obtenir le produit de ces deux polynômes, $ c (x) = p (x) q (x) $, via une force brute, nous devons calculer de nouveaux coefficients via Convolution $ Left (c_k = sum_ {i = 0} ^ k a_i b_ {ki} droit) $ qui prend $ mathcal { theta} (n ^ 2) $ time.

Cependant, si nous voulions évaluer ce produit avec une entrée donnée $ x $, nous pouvons évaluer séparément les deux polynômes $ p (x) $ et $ q (x) $, puis multiplier les deux résultats scalaires. Dans l'ensemble, cela prendrait un temps $ mathcal { theta} (n) $ pour deux évaluations et une multiplication scalaire. Cela nous permet d'éviter d'avoir à faire des convolutions et serait plus rapide que $ mathcal { theta} (n ^ 2) $.

Question: En ce qui concerne l'évaluation du produit de deux polynômes, est-ce en fait $ mathcal { theta} (n) $ en utilisant la méthode ci-dessus ou sommes-nous encore condamnés à $ mathcal { theta} (n ^ 2) $?

Je suis conscient qu'il existe un moyen plus rapide de le faire dans $ Mathcal {o} (n log n) $ time via Fast Fourier Transform, mais je suis plus curieux de la nécessité des calculs de convolution. Je soupçonne que c'est plus si nous nous soucions d'obtenir les coefficients du produit que l'évaluation réelle, comme dans nous nous soucions plus de savoir $ {c_0, c_1, c_2, dotsc } $ que $ c (x) = p (x ) Q (x) $.