Från Googlehemsida

Hoppa till: navigering, sök

Tidkomplexitet: O(n*log(n))


FFT är en dekompositionsalgoritm som i tid O(n log n) transformerar ett n-tegradspolynom i koefficientform till punkt-värdeform eller tvärtom. När man gått över till punkt-värdeform kan polynommultiplikationen enkelt utföras i linjär tid. Därför tar multiplikation av två n-tegradspolynom tid O(n log n) med FFT.