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?