FFT dla równań zawierających terminy z różnymi wykładnikami

Jestem nowy w FFT, więc jestem nieco zdezorientowany niektórymi pojęciami. Do tej pory przykłady FFT, które widziałem dla mnożenia równań, obejmują równania z kolejnymi wykładnikami (tj.A(x) = 1 + 3x + 5x^2 +... iB(x) = 4 + 6x + 9x^2 + ... iC(x) = A(x)*B(x)). Jednak możliwe jest użycie FFT na dwóch równaniach, które nie mają równych wykładników? Na przykład, czy możliwe jest użycie FFT do pomnożenia:

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

i

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

wO(nlogn) czas?

Jeśli nie, czy istnieją przypadki, w których będzie działać środowisko wykonawczeO(nlogn)? Na przykład, jeśli liczba terminów w produkcie wynosiO(n) zamiastO(n^2)?

Nawet jeśli czas działania jest większy niżO(nlogn), jak możemy użyć FFT, aby zminimalizować czas działania?

questionAnswers(1)

yourAnswerToTheQuestion