Effizienz und Komplexität
Im folgenden Kapitel beschäftigen wir uns mit der Analyse von Algorithmen. Dazu muss eindeutig geklärt werden, wie Algorithmen bewertet werden.
Neben dem korrekten Lösen eines Problems, bestehen verschiedene weitere Anforderungen. Wir wollen auch, dass er die Lösung möglichst effizient ermittelt. Effizient bedeutet hierbei, die Berechnung einer Lösung in einer möglichst kurzen Zeit durchzuführen und dabei wenig Speicherplatz zu benötigen.
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 Anzahl 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.