3. Effizienz von Algorithmen

Wir haben schon mehrfach gesehen, dass ein algorithmisches Problem nicht gelöst ist, wenn irgendein korrekter Algorithmus dafür gefunden werden kann. Eine wichtige Frage ist immer auch, ob das Verfahren in vertretbarer Zeit terminiert oder nicht. Ein Sortierverfahren, das zwar richtig sortiert, das für die Sortierung aber Monate aufwenden muss, ist praktisch wertlos. Darum muss die Frage nach der Effizient von Algorithmen in der Algorithmik eine zentrale Rolle spielen. Und genau darum wollen wir uns in Kap. 3 kümmern. Zuerst einmal ist a priori gar nicht klar, wie man den Aufwand eines Algorithmus messen soll. In Sekunden? Das hätte den Nachteil, dass der Aufwand rechnerspezifisch ist, denn dann hätte ein Algorithmus ja je nach Rechner, auf dem er läuft, einen anderen Aufwand. Soll man die Schritte des Algorithmus zählen? Aber was ist genau ein einzelner Schritt? Und wenn einmal klar ist, wie man die Effizienz eines Algorithmus angeben kann, dann stellen sich sofort weitere, anspruchsvollere, aber auch interessantere Fragen: Kann man die Effizienz eines Algorithmus verbessern? Ist es möglich, für ein und dasselbe Problem mehrere Algorithmen zu schreiben, die sich im Aufwand stark unterscheiden? Und gibt es allenfalls einen schnellstmöglichen Algorithmus? Und wie kann man das einsehen? Es sind solche Fragen, die uns in diesem Kapitel anstacheln werden. Antworten sind teilweise alles andere als leicht zu finden, aber es ist ein überaus faszinierendes Gebiet, dem wir hier erste zaghafte Besuche abstatten.