Digital Signal Processing Reference
In-Depth Information
A.3 Algorithmische Komplexitat und
O
-Notation
A
Mathematische Notation
Unter
”
Komplexitat“ versteht man den Aufwand, den ein Algorithmus
zur Losung eines Problems benotigt, in Abhangigkeit von der so genann-
ten
”
Problemgroße“
N
. In der Bildverarbeitung ist dies ublicherweise
die Bildgroße oder auch beispielsweise die Anzahl der Bildregionen. Man
unterscheidet ublicherweise zwischen der
Speicher
komplexitat und der
Zeit
komplexitat, also dem Speicher- bzw. Zeitaufwand eines Verfahrens.
Ausgedruckt wird die Komplexitat in der Form
O
(
N
), was auch als
”
big
Oh“-Notation bezeichnet wird.
Mochte man beispielsweise die Summe aller Pixelwerte eines Bilds der
Große
M
N
Schritte (Additionen)
erforderlich, das Verfahren hat also eine Zeitkomplexitat
”
der Ordnung
MN
“, oder
×
N
berechnen, so sind dafur i. Allg.
M
·
O
(
MN
)
.
Da die Zahl der Bildzeilen und -spalten eine ahnliche Großenordung
aufweist, werden sie ublicherweise als identisch (
N
) angenommen und
die Komplexitat betragt in diesem Fall
(
N
2
)
.
O
Die direkte Berechnung der linearen
Faltung
(Abschn. 6.3.1) fur ein Bild
der Große
N
×
N
und einer Filtermatrix der Große
K
×
K
hatte beispiel-
(
N
2
K
2
). Die
Fast Fourier Transform
(FFT,
s. Abschn. 13.4.2) berechnet das Spektrum eines Signalvektors der Lange
N
=2
k
in der Zeit
weise die Zeitkomplexitat
O
(
N
log
2
N
).
Dabei wird eine konstante Anzahl zusatzlicher Schritte, etwa fur die
Initialisierung, nicht eingerechnet. Auch multiplikative Faktoren, bei-
spielsweise wenn pro Pixel jeweils 5 Schritte erforderlich waren, werden
in der
O
-Notation konnen
daher Algorithmen in Bezug auf ihre E
zienz klassifiziert und verglichen
werden. Details dazu finden sich in jedem Buch uber Computeralgorith-
men, wie z. B. [2].
O
-Notation nicht berucksichtigt. Mithilfe der
O
