4.5 Komplexität von Algorithmen

Zur Beurteilung des Lösungsaufwandes eines konkreten Programms, z.B. für die Ermittlung der numerischen Lösung eines linearen Gleichungssystems auf einem bestimmten Computer bei festgelegten Daten, genügt eine Zeitmessung (mit der "eingebauten Uhr" des Computers oder von Hand). Zählt man hingegen die erforderlichen Berechnungsschritte, so kommt man zu einer Beurteilung, die von einem speziellen Computer und den Daten des konkreten Problems unabhängig ist. Damit hat man eine abstrakte Beschreibungsform zur Beurteilung des Lösungsaufwandes von Algorithmen gefunden.

Die Komplexität eines Algorithmus ist ein Maß für die Arbeit, die bei dessen Abarbeitung zu verrichten ist. Sie ist nicht nur ein Charakteristikum des Lösungsverfahrens, sondern hängt auch vom Schwierigkeitsgrad (Umfang) des behandelten Problems ab. Meist verwendet man zur Charakterisierung des Schwierigkeitsgrades eines Problems nur eine einzige skalare Kennzahl.

Beispiel (Lineare Gleichungssysteme) Der Arbeitsaufwand zur Lösung eines Systems von n linearen Gleichungen in n Unbekannten wird im allgemeinen in Abhängigkeit von der Dimension n als Parameter angegeben. Einem Gleichungssystem

Ax = b

mit

A Rnxn, x, b Rn

wird also die Kennzahl n für den Schwierigkeitsgrad seiner Lösung zugeordnet.

Die Charakterisierung des Schwierigkeitsgrades eines Problems kann unter Umständen auch durch mehr als einen Parameter erfolgen.

Beispiel (Molekulardynamik) (Addison et al. [80]) Bei Algorithmen aus dem Bereich der Molekulardynamik wird die Bewegung von Teilchen in Kraftfeldern simuliert. Bei Implementierungen auf Parallelrechnern wird das betrachtete Gebiet in rechteckige Teilbereiche zerlegt. Jeder Prozessor berechnet laufend die Koordinaten aller Teilchen, die sich gerade in seinem Bereich befinden. Berücksichtigt man direkte Interaktionen zwischen allen Partikeln, dann müssen die Koordinaten aller Partikel auf allen Prozessoren vorhanden sein.

Für den Arbeitsaufwand bei der Berechnung sind die Feinheit der Gebietsunterteilung und die Anzahl der betrachteten Teilchen maßgeblich. In diesem Fall kann die Größe des Problems also durch einen (dreidimensionalen) Parametervektor (Anzahl der Teilintervalle in x- und y-Richtung, Anzahl der Partikel) quantifiziert werden.

Im Vergleich zu skalaren Kenngrößen ist es dann aber schwieriger, Probleme der Größe nach zu ordnen, da man dazu eine Ordnungsrelation für die Parametervektoren braucht.

Aussagen über den Abarbeitungsaufwand eines Algorithmus werden immer in Abhängigkeit von der Schwierigkeitskennzahl des Problems gemacht. Dabei wird meist die Anzahl der Berechnungsschritte, die zur Durchführung des Algorithmus bei einem bestimmten Problemumfang benötigt werden, ermittelt. Trotz der Abstraktion, die in der Verwendung von "Rechenschritten" (anstelle von Zeitmessungen) zum Ausdruck kommt, sind derartige Komplexitätsbetrachtungen nicht von speziellen Hardwareeigenschaften unabhängig. Je nachdem, was als gleichsam "unteilbare" Einheit der Arbeit angesehen wird, ergeben sich signifikante Unterschiede bei der Bestimmung der Komplexität eines Algorithmus. Im Bereich der Numerik ist es üblich, eine Gleitpunktoperation als eine solche elementare Einheit der Arbeit anzusehen.

Beispiel (Gauß-Algorithmus) Der Eliminationsalgorithmus (LU-Zerlegung) zur Lösung linearer Gleichungssysteme benötigt, abhängig von der Anzahl n der Gleichungen,

Wenn man mit dieser Formel den Rechenaufwand des Eliminationsalgorithmus charakterisiert, so vernachlässigt man den Zeitaufwand, der für spezielle algorithmische Maßnahmen (Pivotsuche, Zeilenvertauschen etc.) erforderlich ist.

Jedoch ist es vor allem im Bereich der Parallelrechner möglich und sinnvoll, auch komplexere Operationen (Matrix-Vektor-Operationen, Matrix-Matrix-Operationen, Transponieren einer Matrix, eine schnelle Fourier-Transformation) zu einem elementaren "Rechenschritt" zusammenzufassen (Hockney, Jesshope [236]). Welche Art und Menge an Arbeit in einem solchen nicht weiter zerlegten Berechnungsschritt zusammengefaßt wird, hängt sehr stark vom verwendeten abstrakten Computermodell ab.