Komplexität von Algorithmen und Problemen

Worum geht es hier?

Oft gibt es verschiedene Algorithmen zur Lösung eines Problems. Es stellt sich dann die Frage, welcher dieser Algorithmen der günstigste ist und in der Praxis eingesetzt werden sollte. Ein wesentlicher Aspekt bei der Bewertung von Algorithmen ist der Ressourcenverbrauch. Besonders interessant sind natürlich die Algorithmen, die mit möglichst wenig Rechenzeit und Speicherplatzverbrauch auskommen.

Wir werden uns hier systematisch mit der Einschätzung des Laufzeitverhaltens von Algorithmen beschäftigen. Dabei spielen neben Zeitmessungen Komplexitätsanalysen eine zentrale Rolle.

In den folgenden Abschnitten steht jeweils eine bestimmte Problemstellung im Mittelpunkt. Anhand von Fallstudien werden im jeweiligen Kontext zentrale Fragestellungen zur Komplexität von Algorithmen und Problemen behandelt. Jede Fallstudie kann unabhängig von den anderen betrachtet werden.