Zeitkomplexität eines Problems

Aussagen über die Komplexität aller denkbaren Algorithmen

Bisher haben wir die Zeitkomplexität verschiedener Sortieralgorithmen untersucht und sind zu folgenden Ergebnissen gelangt.

Der Algorithmus selectionsort hat - im günstigsten wie auch im ungünstigsten Fall - eine quadratische Zeitkomplexität. Die zur Beschreibung des Laufzeitverhaltens gewählte Kostenfunktion gehört zur Klasse <O(n²) der asymptotisch quadratisch wachsenden Funktionen.

Der Algorithmus quicksort hat - im günstigsten (und auch durchschnittlichen) Fall - eine logischmisch-lineare Zeitkomplexität. Die zur Beschreibung des Laufzeitverhalten gewählte Kostenfunktion gehört hier zur Klasse O(n*log₂(n)).

Es gibt eine Vielzahl an weiteren Sortieralgorithmen. Die schnelleren dieser Algorithmen haben alle eine logischmisch-lineare Zeitkomplexität. Es stellt sich die Frage, ob es nicht noch schnelleren Sortieralgorithmen gibt - z.B. solche mit einer linearen Zeitkomplexität - und, ob es auch eine Art

untere Schranke für die Zeitkomplexität gibt, die von keinem Sortieralgorithmus unterschritten werden kann. Diese Fragen betreffen die Komplexität des Sortierproblems.

Zur Beschreibung der Komplexität eines Problems muss man folglich Aussagen über alle möglichen Algorithmen zur Lösung des Problems machen, indem man zeigt, dass ein bestimmter Ressourcenverbrauch bei all diesen Algorithmen erforderlich ist und von keinem Algorithmus unterschritten werden kann. Die Schwierigkeit beim Nachweis solcher Aussagen besteht darin, dass man den Nachweis über alle denkbaren - d.h. bis jetzt gefundenen und auch noch nicht bekannten - Algorithmen führen muss.

Wir werden im Folgenden einen solchen Nachweis für (fast) alle denkbaren Sortieralgorithmen führen und auf diese Weise die Komplexität des Sortierproblems beschreiben.