Oft ist man nicht an der Zahl der Operationen in einem konkreten Fall, sondern vielmehr am qualitativen Verlauf
der Anzahl der Berechnungsschritte in Abhänigkeit von den Problemparametern interessiert. Vor allem für die Charakterisierung von
großen Problemen ist die asymtotische Komplexität vom großer Bedeutung.
Ordung der Komplexität :
Die von einem Parameter p abhängende Komplexität K(p) hat die Ordnung von f(p), falls es
die Konstanten b und c gibt, für die
(Sprich: Groß O von von f(p)).
Algorithmen mit Komplexität bestimmter Ordnung werden in asymptotischen Komplexitätsklassen zusammengefaßt.
Hier die Wichtigsten :
Diese Tablelle ist nach aufsteigender asymptotischer Komplexität geordnet.
Die asymptotische Komplexität wird zur groben Klassifizierung von Algorithmen zur Lösung eines bestimmten
Problems herangezogen. Haben zwei Algorithmen dieselbe asymptotische Komplexität, so bedeutet das, daß ihr Abarbeitungsaufwand
bei größer werdenden Problemen gleich schnell steigt.
Beispiel (Sortieralgorithmen)
Bei Sortieralgorithmen ist der obengenannte Parameter p die Anzahl der zu sortierenden Elemente. Der Arbeitsaufwand wird
anhand der Anzahl an nötigen Vergleiche zweier Elemente charakterisiert. (Dieser ist natürlich neben dem Algorithmus auch von der
Anordnung der Elemente abhängig.)
Bei Sortieralogrithmen lassen sich nun z.B. Minimum-Suche und Quicksort in einer Algorithmenklasse zusammenfassen, da sie beide im
worst-case Fall eine quadratische Komplexität aufweisen.
Die asymptotische Komplexität von Heapsort und Sortieren durch Mischen ist unabhängig von der Anordnung der Elemente bei Start
des Algorithmus immer gleich O(k log k). Diese Verfahren sind daher gemeinsam in der Klasse asymptotisch effizienter Algorithmen.
Im Gegensatz zur Komplexität von Algorithmen läßt sich die Komplexität von Problemen nicht so leicht
bestimmen, gibt es doch zu einem Problem meist mehrere Lösungsalgorithmen von unterschiedlicher Komplexität.
Der Begriff der Komplexitätsklasse ist jedoch gut übertragbar :
In einer Komplexitätsklasse von Problemen liegen alle Probleme, die mit Algorithmen einer bestimmten Komplexitätsklasse lösbar sind.
Die Komplexität eines Problems ist dann definiert durch die minimale Komplexitätsklasse, in der das Problem liegt.
Meist erweist es sich aber als schwierig, diese minimale Komplexitätsklasse zu bestimmen, denn dafür müßte man durch Analyse die untere Schranke
des Arbeitsaufwands (des Problems) bestimmen und einen Algorithmus finden, dessen asymptotische Komplexität gleich dieser Schranke ist.
Beispiel (Lineare Gleichungssysteme)
Der Gaußalgorithmus zur Lösung von n linearen Gleichungen ist ein O(n³)-Algorithmus. Daraus zu schließen, auch die Komplexität des Problems
der Lösung eines linearen Gleichungssystems sei kubisch, ist falsch. Das bestätigt sich spätestens dann, wenn jemand einen Algorithmus (zur Lösung des Problems) von
geringerer Komplexität findet. Im Fall der Lösung von n linearen Gleichungen gibt es einen explizit bekannten O(n2.376) Algorithmus, sodaß man die intuitive
Komplexität der Lösung linearer Gleichungssysteme ungefähr einschränken kann :
Aus dem Wissen, daß das Problem in der Klasse der O(n2.376)-Lösbaren Probleme liegt und jeder Algorithmus mindestens n² Zugriffe auf die Matrixelemente
benötigt, läßt sich die Komplexität des Problems folgendermaßen einschränken :
Definition der Matrizenmultiplikation ("Zeilen-mal-Spalten-Algorithmus") (J.Sylvester, 1850):
Dieser Algorithmus erfordert n³ Multiplikationen und n²(n-1) Additionen, seine asymptotische Komplexität bezüglich seiner
arithmetischen Operationen (Additionen und Multiplikationen) ist daher kubisch.
Hundert Jahre lang hatte niemand eine Idee für einen besseren Algorithmus, bis S. Winograd 1967 einen Weg fand, die Hälfte der
n³ Multiplikationen (des oben genannten Algorithmus) durch Additionen zu ersetzen.
Da die damaligen Computer (Gleitpunkt-)Additionen wesentlich (zwei bis dreimal) so schnell ausführten als (Gleitpunkt-)Multiplikationen, war dieser Algorithmus damals
viel schneller als der Alte. Heute
Kurz nach Winograd's Veröffentlichung fand V. Strassen eine neue Methode zur Matrizenmultiplikation, deren Komplexitätsordnung mit
deutlich unter der kubischen Komplexität der Methode von Sylvester lag (
).
Strassen warf damals auch die Frage auf, ob es einen kleinsten Exponenten w gibt, sodaß jede Matrizenmultiplikation in O(nw) Operationen
ausgeführt werden kann. Natürlich gilt dabei immer 
, da jedes Element der beiden Matrizen mindestens in einer Operation als Operand vorkommen muß.
Bis heute ist das Minimum dieser Exponenten (die asymptotische Komplexität des Problems der Matrizenmultiplikation) noch nicht gefunden, zur Zeit gilt der "Weltrekord" von Ende 1990 mit
w = 2.376.
Hier die historische Entwicklung von O(nw):
