Effizienz von Algorithmen SS09

Effizienzbegriff

Ein Algorithmus heißt effizient, wenn er ein vorgegebenes Problem mit möglichst geringem Ressourcenaufwand (Zeit, Speicher) löst.

Diese Formulierung muss weiter präzisiert werden. Außerdem ist zu beachten, dass Zeit und Speicher ineinander "umwandelbar" sind, d.h. wenn man bei der Modellierung knappen Speicher wählt, kann es sein, dass der Algorithmus Zusatzaufwand betreiben muss, da gewisse Daten zwischengerechnet werden müssen und eben nicht direkt zur Verfügung stehen.

Beispiel: Dublettensuche in einer Liste

Vereinfachend nehmen wir an, dass es sich um Listen mit Zufallszahlen handelt. Sobald ein doppeltes Listenelement gefunden wurde, soll das Verfahren mit der Ausgabe dieses Elements stoppen, anderenfalls stoppt der Algorithmus ohne Ausgabe eines Wertes.

Das Programm aus dem ersten Lösungsvorschlag arbeitet mit quadratischem Aufwand:

<eval id="4ba10f230009b">(random 10)</eval>