Polynommultiplikation

Autor/Urheber:

Algomath

Shortlink:

https://dewiki.de/b/219c18

Quelle:

Wikimedia Commons

Größe:

1276 x 532 Pixel (173577 Bytes)

Beschreibung:

Schnelle Multiplikation zweier Polynome ${\displaystyle p_{a}(x)=\sum \nolimits _{i=0}^{n}a_{i}x^{i}}$ und ${\displaystyle p_{b}(x)=\sum \nolimits _{i=0}^{n}b_{i}x^{i}}$ zu ${\displaystyle p_{c}(x):=p_{a}(x)\cdot p_{b}(x)=\sum \nolimits _{i=0}^{n}c_{i}x^{i}}$. Dabei werden zunächst die zu den beiden Polynomen ${\displaystyle p_{a}}$ und ${\displaystyle p_{b}}$ korrespondierenden Koeffizientenfolgen durch schnelle Fourier-Transformation in Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$ transformiert, sodass sich die zum Polynom ${\displaystyle p_{c}}$ korrespondierende fouriertransformierte Koeffizientenfolgen durch komponentenweise Multiplikation in Laufzeit ${\displaystyle {\mathcal {O}}(n)}$ ergibt. Diese wird schlussendlich durch schnelle inverse Fourier-Transformation in Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$ rücktransformiert. Die Gesamtlaufzeit liegt in ${\displaystyle {\mathcal {O}}(n\log n)}$ und ist damit asymptotisch effizienter im Vergleich zur klassischen Polynommultiplikation mit Laufzeit ${\displaystyle {\mathcal {O}}(n^{2})}$.

Lizenz:

CC0

Bild teilen: