Kleines Nachschlagewerk Informatik
Komplexität
Was muss man wissen?
Wenn Programme Daten verarbeiten, dann hängt die Zeit für die Verarbeitung und der benötigte Speicherplatz oft von der Anzahl der Daten ab. Die Art, wie die Laufzeit bzw. der Speicherplatz von der Anzahl der Daten abhängt, beschreibt die Komplexität.

Man muss die zugehörigen Komplexitätsklassen (konstant, linear, quadratisch, kubisch, exponentiell, logarithmisch und linear logarithmisch (nlogn)) kennen.

Man sollte zu jeder Klasse ein Beispiel kennen. Dies betrifft sowohl den Speicherverbrauch als auch die Laufzeit.

Man muss wissen, dass (analog zur Funktionsuntersuchung in der Mathematik) in einer Summe der am stärksten wachsende Summand das Endergebnis bestimmt.

Man muss naturlich wissen, dass Komplexität etwas mit der Entwicklung der Laufzeit bzw. dem Speicherverbrauch zu tun hat und kein Merkmal der genauen Laufzeit bei einer festen Datenmenge ist.

Man muss wissen, dass es für einen Sachverhalt oft verschiedene Algorithmen unterschiedlicher Komplexität gibt (siehe z.B. Fibonacci-Folge).

Bei der Analyse von Speicher ist auch der Speicher für Parameterübergabe und Rücksprungadressen zu beachten. Die gilt vor allem für rekursive Aufrufe.
Was muss man können?
Man muss Algorithmen bzgl. der Komplexität abschätzen können. Dazu gehört erstens die Analyse des Quelltextes (Schleifen, geschachtelte Schleifen, Rekursionen).

Die zweite Art, Komplexität abzuschätzen, ist die Analyse von Beispieldaten (n=1,2,3,... bzw. Verdopplung etc.). Baumartige Strukturen helfen bei der Visualisierung.

Die dritte Art ist der Vergleich mit bekannten Algorithmen, deren Komplexitätsklasse bekannt ist.
Weitere Fragen