~XIV: Die Laufzeit der diskreten Fourier-Transformation

Eine zentrale Frage der Informatik ist, wie effizient ein Algorithmus ist. Beispielsweise, um zu überlegen, ob man eine gewisse Berechnung auch effizienter durchfphren kann. Stellt man sich einen Algorithmus wie eine Schulaufgabe vor, so ist Effizienz der Verbrauch an Papier und Bleistift, aber auch an Denk/Rechenzeit. Es ist schließlich unpraktikabel, wenn ein entworfener Algorithmus, also ein Programm, das etwas berechnen soll, so lange rechnet, dass das Ergebnis danach nicht mehr nützlich ist. Zum Versenden des Finales der Rugby-WM als Stream wäre es deutlich unpraktisch, wenn die Berechnung des Datenstromes vom unkomprimierten Kamerabild zu einem Video, das auch auf einem Heimcomputer noch übers Internet empfangbar ist, länger dauert, als das Spiel selbst.
Doch wie misst man die Effizienz eines Algorithmus am Computer? Und, ist die Fourier-Transformation effizient?

Bei der ersten Frage könnte man beginnen und einfach die Zeit messen, die ein Algorithmus benötigt, wenn er bestimmte Eingaben bekommt. Doch dabei stellen sich viele Probleme: Man müsste repräsentative Eingaben auswählen und für die Reproduzierbarkeit der Messungen den Computer sehr genau spezifizieren und sichergehen, dass kein zur Berechnung benötigter Teil kaputt ist. Insgesamt ist das für ein komplexes System wie einen Computer zu kompliziert. Insbesondere sind die Messungen aber auch nach wenigen Jahren veraltet, weil es dann viel schnellere Computer gibt, siehe dazu auch Mooresches Gesetz.

Um von einem speziellen Computer unabhängig zu sein, sind Laufzeit- oder Speicherverbrauchsbetrachtungen also rein theoretisch. Ein Algorithmus ist, kurz gesagt, nichts anderes als eine Folge von Rechenanweisungen, am häufigsten die Addition und die Multiplikation. Beide benötigen auf einem speziellen Computer eine gewisse Zeit, um durchgeführt zu werden; die Multiplikation üblicherweise ein wenig mehr als die Addition. Auch davon sei hier abstrahiert, beide werden mit \(1\) gezählt.

Für eine feste Eingabegröße \(N\), bei der diskreten Fourier-Transformation also \(N\) Werte \(y_j, j=0,\ldots,N-1\), lassen sich dann die benötigten Additionen und Multiplikationen zählen. Für einen Wert \(\hat y_k\) des Ergebnisses besagt die FormelHier auch in der Schreibweise, in der die Abtastpunkte \(x_j\) fest eingesetzt wurden \[ \hat y_k = \frac{1}{N}\sum_{j=0}^{N-1} y_j\textrm{e}^{-2\pi\textrm{i}\frac{kj}{N}}, \] dass zunächst für jeden Summanden eine Multiplikation \(y_j\cdot\textrm{e}^{-2\pi\textrm{i}\frac{kj}{N}}\) zu berechnen ist und anschließend die \(N\) Werte zusammenaddiert werden müssen. Dies ergibt \(N\) Multiplikationen und \(N-1\) Additionen. Allerdings muss die Berechnung für jedes \(k=0,\ldots,N-1\), also \(N\) mal berechnet werden und das ganze für die reellen und die imaginären Einträge. Zusammen also \[ 2N(N + N-1) = 2N^2-N\quad\text{Rechenschritte}. \]

Was bedeutet das nun in der Praxis? Dazu listet die folgende Tabelle 1 ein paar Beispiele auf.

N248163264128
Rechenschritte der DFT12562409924 03216 25665 280
Anzahl Rechenoperationen für Fourier-Transformationen verschiedener Eingabelänge

Insbesondere sind diese Zahlen unabhängig davon, welche spezielle Funktion abgetastet wurde, lediglich die Anzahl Abtastpunkte ist hier von Interesse. Von einer Spalte zur nächsten verdoppelt sich die Eingabegröße: Von zwei Werten (\(y_0,y_1\)) auf vier (\(y_0,y_1,y_2,y_3\)), auf acht und so weiter. Betrachtet man dazu die Anzahl Rechenoperationen, so werden diese jeweils mehr als Vervierfacht. Von der ersten zur letzten Spalte wird die Eingabe um den Faktor 64 vergrößert (von 2 auf 128), die Rechenoperationen vergrößern sich jedoch um den Faktor 5 440. Eine ganze Menge. Möchte man also statt zwei Sekunden Video, etwa vom obigen Rugby-WM-Finale, 128 Sekunden umrechnen, benötigt man mehr als das Fünftausendfache an Zeit. Vom ganzen Spiel, das vielleicht zwei Stunden dauert, mal nicht zu reden. Dabei wurde in der Betrachtung noch nicht berücksichtigt, dass wir bisher von eindimensionalen Daten, also \(x_j\) auf einer Linie sprachen und ein Video dreidimensional —  zweidimensionales Bild und die Zeit mdash; – ist.

In der Theorie vereinfacht man diese Berechnung noch etwas, damit man das Wesentliche schneller sieht. Die Ursache für diese drastische Zunahme ist in dem ersten, quadratischen Term versteckt, dem \(2N^2\). Der hintere Teil verringert die Anzahl, hat jedoch für große \(N\), keinen Einfluss mehr. Den Torfaktor \(2\), den können wir auch vernachlässigen, denn der kann auch noch davon abhängen, wie schnell nun die Multiplikation auf dem Computer wirklich realisiert ist. Wichtig ist wirklich nur der Term mit dem meisten Einfluss, der hier das \(N^2\) ist. Dazu wurde die Landau-Symbolik eingeführt. Bei diesen wird nur der Term mit der größten Wachstumsrate bedacht, der bei Polynomen das Monom mit dem größten Exponenten ist. Bei uns ist dies das \(N^2\) und man schreibt somit die Laufzeit der diskreten Fourier-Transformation als \(\mathcal O(N^2)\). Die diskrete Fourier-Transformation hat also eine Laufzeit, die sich verhält, wie \(N^2\), da für große Werte von \(N\) der hintere lineare Term \(-N\) keinen Einfluss mehr hat. Genauso haben weitere Konstante Zeiten, wie das Hochfahren des Computers oder keinen Einfluss mehr, wenn \(N\) groß genug ist.

Eine Laufzeit von \(\mathcal O(N^2)\) bedeutet in der Symbolik, dass der Algorithmus höchstens so schnell wächst wie \(N^2\). Dieser Beitrag zeigt mit seiner Betrachtung der Laufzeit ja gerade, dass \(N^2\) möglich ist, noch schlechter, also langsamer, könnte man das schon programmieren, aber zumindest \(N^2\) ist möglich. Was diese Notation nicht aussagt, ist, ob es nicht noch schneller zu berechnen geht. Die \(\mathcal O\)-Notation bezieht sich immer auf eine obere Grenze des Wachstums, wobei der Vorfaktor vor dem Term, hier die \(2\) vor dem \(N^2\) vernachlässigt wird. Bleibt also die Frage: Geht das schneller?

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.