FFT pour la forme expansée de la multiplication de l'équation

Question

Je sais comment utiliser la FFT pour multiplier deux équations en O $ (n \ log \, n) $ temps, mais est-il un moyen d'utiliser FFT pour calculer l'équation développée avant la simplification?

Par exemple, si vous multipliez $ A (x) = 1 + 2x + 6x ^ 2 $ et $ B (x) = 4 + 5x + 3x ^ 2 $ de telle sorte que vous obtenez $ C (x) = A (x) \ cdot B (x) = 4 + 5x + 3x ^ 2 + 8x + 10x ^ 2 + 6x ^ 3 + 24x ^ 2 + 30x ^ 3 + 18x ^ 4 $ sans aller directement à la réponse simplifiée?

En outre, il est possible d'utiliser FFT pour faire cette multiplication de forme développée dans O $ (n \ log \, n) $ temps? Si oui, pouvez-vous me montrer comment appliquer FFT à ce scénario?

Answer 1

L'algorithme trivial qui multiplie chaque monôme en $ A $ par chaque monôme en $ B $ prend du temps $ O (| A | \ cdot | B |) $ (où $ | A | $ est le nombre de monômes en $ A $ ou $ \ deg A + $ 1, en fonction de la représentation), qui est du même ordre de grandeur que la taille de la sortie, et donc optimale. Vous avez seulement besoin FFT si vous voulez calculer réellement le produit $ AB $. En particulier, il est aucun moyen pour calculer votre fonction dans le temps $ O (n \ log n) $, simplement parce que la longueur de la sortie est $ \ Omega (n ^ 2) $.