Eu sou novo em FFTs, então estou um pouco confuso em alguns conceitos. Até agora, os exemplos de FFT que vi para a multiplicação de equações envolvem equações com expoentes consecutivos (ou seja,A(x) = 1 + 3x + 5x^2 +... eB(x) = 4 + 6x + 9x^2 + ... eC(x) = A(x)*B(x)). No entanto, é possível usar FFT em duas equações que não possuem expoentes iguais? Por exemplo, é possível usar FFT para multiplicar:

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

e

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

emO(nlogn) Tempo?

Se não, existem casos em que o tempo de execução seráO(nlogn)? Por exemplo, se o número de termos no produto forO(n) ao invés deO(n^2)?

Mesmo se o tempo de execução for maior queO(nlogn), como podemos usar FFT para minimizar o tempo de execução?