Soy nuevo en FFT, por lo que estoy un poco confundido con algunos conceptos. Hasta ahora, los ejemplos de FFT que he visto para la multiplicación de ecuaciones involucran ecuaciones con exponentes consecutivos (es decir,A(x) = 1 + 3x + 5x^2 +... yB(x) = 4 + 6x + 9x^2 + ... yC(x) = A(x)*B(x)). Sin embargo, ¿es posible usar FFT en dos ecuaciones que no tienen exponentes iguales? Por ejemplo, es posible usar FFT para multiplicar:

A(x) = 1 + 3x^2 + 9x^8

y

B(x) = 5x + 6 x^3 + 10x^8

enO(nlogn) ¿hora?

Si no, ¿hay casos en que el tiempo de ejecución seráO(nlogn)? Por ejemplo, si el número de términos en el producto esO(n) en lugar deO(n^2)?

Incluso si el tiempo de ejecución es más queO(nlogn), ¿cómo podemos usar FFT para minimizar el tiempo de ejecución?