Ich bin neu in FFTs, daher bin ich bei einigen Konzepten etwas verwirrt. Bisher beinhalten die FFT-Beispiele, die ich für die Gleichungsmultiplikation gesehen habe, Gleichungen mit aufeinanderfolgenden Exponenten (d. H.A(x) = 1 + 3x + 5x^2 +... undB(x) = 4 + 6x + 9x^2 + ... undC(x) = A(x)*B(x)). Es ist jedoch möglich, FFT für zwei Gleichungen zu verwenden, die nicht die gleichen Exponenten haben. Ist es zum Beispiel möglich, mit FFT zu multiplizieren:

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

und

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

imO(nlogn) Zeit?

Wenn nicht, gibt es Fälle, in denen die Laufzeit sein wirdO(nlogn)? Zum Beispiel, wenn die Anzahl der Begriffe im Produkt istO(n) anstattO(n^2)?

Auch wenn die Laufzeit mehr alsO(nlogn), wie können wir FFT verwenden, um die Laufzeit zu minimieren?