Komplexität von Algorithmen

Die Komplexitätstheorie untersucht, welche Berechnungsprobleme sich effizient algorithmisch lösen lassen. Dazu misst man den Aufwand eines Algorithmus – vor allem seine Laufzeit und seinen Speicherbedarf.

Was misst die Komplexität?

Zwei Komplexitätsmaße stehen im Mittelpunkt:

• Zeitkomplexität (Laufzeit): Wie viele Rechenschritte benötigt der Algorithmus in Abhängigkeit von der Eingabegröße?
• Raumkomplexität (Speicherbedarf): Wie viel Speicher braucht er dabei?

Die Komplexitätsklassen P und NP

Anhand dieser Maße werden Probleme in Klassen eingeteilt. Besonders wichtig sind:

• Klasse P: Probleme, die sich in polynomieller Zeit – also effizient – lösen lassen.
• Klasse NP: Probleme, deren Lösung sich effizient überprüfen lässt, für die aber kein effizienter Lösungsweg bekannt ist.

NP-vollständige Probleme und das P-NP-Problem

NP-vollständige Probleme sind die schwersten Probleme in NP. Sie treten in vielen Bereichen auf – VLSI-Design, Netzwerk-Optimierung, Operations Research. Bekannte Beispiele sind das Problem des Handlungsreisenden und das Partitionierungsproblem. Das Erstaunliche: Alle diese Probleme sind äquivalent – findet man für ein einziges einen effizienten Algorithmus, sind sie alle effizient lösbar. Ob das möglich ist, ist die berühmte offene Frage „P = NP?". Praktisch behilft man sich bei solchen Problemen oft mit Heuristiken und Approximationsverfahren.

Zusammenfassung und Lerntipp

Auf den Punkt: Die Komplexität misst Laufzeit und Speicherbedarf eines Algorithmus. Die Klassen P und NP sowie NP-vollständige Probleme stehen im Zentrum – mit der offenen Frage „P = NP?".

Lerntipp: Abstrakte Klassen wie P, NP und NP-vollständig werden greifbar, wenn du sie über konkrete Beispiele (Handlungsreisender) und die Kreis-des-Wissens-Methode verknüpfst.