Komplexitätsbetrachtungen

Zeitkomplexität eines Algorithmus

Bei Aufwandsabschätzungen interessiert man sich (u.a.) für die Frage: In welcher Weise wächst der Rechenaufwand mit wachsender Problemgröße? Wächst der Aufwand zum Beispiel linear, polynomial, exponentiell oder gar überexponentiell?

Die Zeitkomplexität eines Algorithmus wird durch Kostenfunktionen beschrieben. Solche Funktionen liefern in der Regel Abschätzungen des Rechenaufwands für bestimmte Sonderfälle (best case, worst case).

Die Aufwandsbetrachtungen im letzten Abschnitt haben gezeigt, dass das bisher benutzte einfache Probedivisionsverfahren im ungünstigsten Fall eine exponentielle Zeitkomplexität hat.

Anwendbarkeit eines Algorithmus

Algorithmen, die eine exponentielle oder überexponentielle Zeitkomplexität haben, gelten als praktisch nicht anwendbar. Nur für sehr kleine Problemgrößen liefern sie in akzeptabler Zeit ein Ergebnis. Mit wachsender Problemgröße explodieren die Kosten, so dass Ergebnisse nicht mehr in akzeptabler Zeit zu erwarten sind.

Der bisher durchgeführten Analysen zeigen, dass der bisher benutzte einfache Probedivisionsalgorithmus nicht anwendbar ist, wenn man sehr große Zahlen mit weniger sehr großen Primfaktoren verarbeiten lässt.

Zeitkomplexität eines Problems

Sicher gibt es Algorithmen, die das Faktorisierungsproblem besser lösen als der hier vorgestellte naive Probedivisionsalgorithmus. Es stellt sich die Frage, ob es unter diesen Algorithmen Kandidaten gibt, die das Faktorisierungsproblem mit einer nicht-exponentiellen Zeitkomplexität lösen.

Noch allgemeiner kann man nach der Zeitkomplexität des Faktorisierungsproblems fragen. Die Zeitkomplexität eines Problems wird dabei durch eine untere Schranke für Kostenfunktionen von Algorithmen zur Lösung des Problems beschrieben.

Bis jetzt sind solche unteren Schranken für das Faktorisierungsproblem nicht gefunden worden. Es wurde auch noch kein Algorithmus entwickelt, der das Faktorisierungsproblem mit nicht-exponentieller Zeitkomplexität löst. Alle bisher entwickelten Algorithmen sind demnach - im Fall großer Ausgangszahlen - praktisch nicht anwendbar. Diesen Sachverhalt nutzt man bei der Entwicklung kryptologische Verfahren aus (vgl. auch Das RSA-Verfahren).

Aufgabe 1

Überlege dir Verbesserungen des Probedivisionsalgorithmus. Versuche auch, die Auswirkungen von Verbesserungen auf den Berechnungsaufwand herauszufinden.