Effizienz und Komplexität

In diesem Modul beschäftigen wir uns mit der Analyse von Algorithmen. Demzufolge benötigen wir Techniken zur Bewertung von Algorithmen.

Es bestehen verschiedene Anforderungen an einen Algorithmus, nicht nur, dass er ein Problem korrekt löst. Wir wollen auch, dass er die Lösung möglichst effizient ermittelt. Effizient bedeutet hierbei, dass die Lösung in möglichst kurzer Zeit berechnet werden kann und dabei wenig Speicherplatz verbraucht wird.

Effizienz

Ein Algorithmus heißt effizient, wenn er ein vorgegebenes Problem mit möglichst geringem Aufwand an Ressourcen löst. Dies umfasst die benötigte Laufzeit (bzw. die Anzahl der auszuführenden Operationen), die Größe des Speichers und die Zahl der Zugriffe auf den Hintergrundspeicher.

Komplexität

Die Komplexität eines Algorithmus bzw. einer berechenbaren Funktion ist der zur Berechnung erforderliche Aufwand an Betriebsmitteln („Rechenaufwand“) wie Speicherplatz, Rechenzeit, benötigte Geräte usw.