Wikipedia · einfach zusammengefasst · Stand
Komplexität (Informatik)
Die Komplexität eines Problems ist zum Beispiel entscheidend für die Kryptographie und insbesondere für die asymmetrische Verschlüsselung: So verlässt sich …
Inhalt5 Abschnitte
Bedeutungen des Begriffs
Komplexität bezeichnet in der Informatik je nach Teilgebiet unterschiedliche Eigenschaften. Bei Algorithmen und Problemen geht es um den Verbrauch von Ressourcen wie Rechenzeit und Speicher. In der Informationstheorie bezeichnet der Begriff den Informationsgehalt von Daten oder Nachrichten. Bei Software beschreibt er vor allem die Zahl und Struktur der Interaktionen und Abhängigkeiten zwischen einzelnen Teilen. Gemeinsam ist diesen Bedeutungen, dass Komplexität ausdrückt, wie aufwendig etwas verarbeitet, beschrieben, erzeugt, verstanden oder verändert werden kann.
Ressourcenbedarf von Algorithmen und Problemen
Die Komplexität eines Algorithmus, auch Aufwand oder Kosten genannt, ist sein Ressourcenbedarf. Er wird meist in Abhängigkeit von der Eingabelänge n angegeben. Für große n schätzt man das Wachstum asymptotisch, also mit Blick auf das Verhalten bei sehr großen Eingaben, mithilfe von Landau-Symbolen ab. Dabei lässt man in der Regel konstante Faktoren und Summanden weg. Die Eingabelänge wird als n = |w| geschrieben und anhand der Anzahl von Bits gemessen, die zur Darstellung der Eingabe benötigt werden.
Am häufigsten betrachtet man zwei Ressourcen: Die Zeitkomplexität gibt die Anzahl der erforderlichen Rechenschritte an, die Platzkomplexität den benötigten Speicher. Grundsätzlich kann die Analyse aber auch eine andere Ressource untersuchen. Entscheidend ist nicht die Laufzeit eines bestimmten Programms auf einem bestimmten Computer, sondern die Skalierbarkeit: Wie wächst der Bedarf, wenn mehr Daten verarbeitet werden? Bei einer Verdopplung der Datenmenge kann sich der Aufwand beispielsweise ebenfalls verdoppeln oder sogar vervierfachen.
Eine übliche Vereinfachung besteht darin, für alle elementaren Operationen denselben Zeitbedarf anzunehmen. Dann kosten etwa die Addition zweier Zahlen und die Multiplikation zweier Zahlen jeweils genau eine Zeiteinheit.
Die Komplexität eines Problems wird über den Ressourcenverbrauch eines optimalen Algorithmus definiert, der dieses Problem löst. Ihre Bestimmung ist schwierig, weil dafür grundsätzlich alle möglichen Algorithmen für das Problem berücksichtigt werden müssen. Algorithmen und Probleme werden nach ihrem Aufwand in Komplexitätsklassen eingeordnet. Mit ihnen lässt sich untersuchen, welche Probleme „gleich schwierig“ oder welche Algorithmen „gleich mächtig“ sind. Ob zwei Klassen gleichwertig sind, kann selbst schwer zu entscheiden sein; ein bekanntes Beispiel ist das P-NP-Problem.
Für die Kryptographie ist die Schwierigkeit eines Problems besonders wichtig. Das RSA-Verfahren verlässt sich auf die Vermutung, dass die Primfaktorzerlegung großer Zahlen nur mit sehr hohem Aufwand berechnet werden kann. Wäre sie leicht möglich, könnte aus dem öffentlichen Schlüssel leicht der private Schlüssel ermittelt werden. Ein Problem, das sogar für einen Computer von der Größe der Erde nicht lösbar wäre, heißt transcomputationales Problem.
Informationsgehalt und Erzeugung von Daten
In der Informationstheorie wird die Komplexität einer Nachricht oder Datenmenge als ihr Informationsgehalt verstanden. Neben der klassischen Definition nach Claude Shannon existieren weitere Ansätze.
Die Kolmogorow-Komplexität, auch Algorithmische Komplexität oder Beschreibungskomplexität genannt, definiert den Informationsgehalt als Größe des kleinsten Programms, das die betrachteten Daten erzeugen kann. Sie beschreibt damit eine absolut optimale Komprimierung: Je kürzer das kleinste erzeugende Programm ist, desto geringer ist nach diesem Ansatz der Informationsgehalt. Gregory Chaitins Algorithmische Informationstheorie präzisiert den Ansatz von Andrei Kolmogorow im Hinblick auf das verwendete Maschinenmodell.
Die Algorithmische Tiefe, auch Logische Tiefe genannt, verwendet dagegen die Zeitkomplexität eines optimalen Algorithmus zur Erzeugung der Daten als Maß für deren Informationsgehalt. Während die Kolmogorow-Komplexität somit nach der kleinsten Programmbeschreibung fragt, betrachtet die Algorithmische Tiefe die zur Erzeugung benötigte Zeit.
Abhängigkeiten, Verständlichkeit und Wartbarkeit
Bei Programmen umfasst Komplexität zahlreiche Eigenschaften, die interne Interaktionen beeinflussen. Dabei wird meist zwischen „komplex“ und „kompliziert“ unterschieden. „Kompliziert“ bedeutet, dass Code, Algorithmen, technisches Design oder Architektur für Programmierer schwer zu verstehen sind. Es handelt sich damit um eine interne Eigenschaft. „Komplex“ bezieht sich dagegen auf die Interaktionen zwischen Teilen eines Programms.
Mit der Anzahl der Abhängigkeiten zwischen Teilen steigt die Zahl der möglichen Interaktionen. Dadurch wird das Gesamtsystem meist auch schwerer zu verstehen und somit komplizierter. Die Komplexität kann so weit anwachsen, dass Menschen das Programm nicht mehr vollständig überblicken können.
Viele Abhängigkeiten erhöhen außerdem das Risiko, dass eine Änderung an einer Stelle unbeabsichtigte Folgen an einer anderen Stelle hat. Dadurch steigt die Wahrscheinlichkeit neuer Fehler. Gleichzeitig wird es aufwendiger, deren Ursachen zu finden und sie zu beheben. Im ungünstigsten Fall wird das Programm faktisch unwartbar, weil die Risiken einer Änderung größer als ihr Nutzen sind. Meir Manny Lehman untersuchte den Zusammenhang zwischen Komplexität und Wartungsaufwand und fasste ihn 1980 in seinen Gesetzen der Softwareevolution zusammen.
Metriken zur Messung
Softwaremetriken sind Kennzahlen, mit denen unterschiedliche Aspekte von Daten, Algorithmen, Programmabläufen und Abhängigkeiten messbar gemacht werden. Meir Manny Lehman und Laszlo Belady untersuchten eine Reihe solcher Metriken.
• Chapins Data-Metrik misst den Anteil der Bedingungs- und Ergebnisdaten an allen verwendeten Daten.
• Elshofs Data-Flow-Metrik setzt die Zahl der Datenverwendungen zur Zahl der Daten ins Verhältnis. Sie hängt mit hoher Kohäsion zusammen. Hohe Kohäsion bedeutet hier, möglichst wenige Variablen häufig zu verwenden.
• Cards Data-Access-Metrik misst die Anzahl der Zugriffe auf externe Dateien und Datenbanken im Verhältnis zur Anzahl dieser Dateien und Datenbanken.
• Henrys Interface-Metrik betrachtet Zugriffe fremder Funktionen oder Methoden auf ein Modul, englisch fan-in, und Aufrufe fremder Funktionen oder Methoden aus einem Modul, englisch fan-out. Diese Werte werden relativ zu allen Funktionen oder Methoden des Moduls gemessen.
• Die McCabe-Metrik, auch Eulers Maß oder Zyklomatische Komplexität genannt, misst die Komplexität eines Ablaufgraphen als Verhältnis der Anzahl seiner Kanten zur Anzahl seiner Knoten.
• McClures Decision-Metrik bestimmt den Anteil der Entscheidungen an allen Anweisungen.
• Sneeds Branching-Metrik setzt die Zahl aller Arten von Verzweigungen zur Summe aller Anweisungen ins Verhältnis.
• Die Halstead-Metrik vergleicht die Zahl verschiedener Wörter, hier Anweisungstypen, mit der Zahl der verwendeten Wörter, hier Anweisungen. Ihr liegt die umstrittene Behauptung zugrunde, dass Code umso einfacher sei, je weniger verschiedene Anweisungstypen verwendet werden.
• NPATH zählt die azyklischen, also nicht in einen Zyklus zurücklaufenden, Pfade durch Funktionen.
• Cognitive Complexity wird von SonarQube gegenüber anderen Metriken zur Messung der Komplexität von Programmen und Programmteilen empfohlen.
Für objektorientiertes Design stellten S. R. Chidamber und C. F. Kemerer 1994 sechs Metriken vor: gewichtete Methoden pro Klasse, Kopplung zwischen Objektklassen, Antworten pro Klasse, Anzahl an Subklassen, Tiefe des Vererbungsbaumes und ungenügende Kohäsion von Methoden.
