Fachkonzept - Effizienz
Unterschiedliches Laufzeitverhalten
Die beiden folgenden Algorithmen berechnen beide den größten gemeinsamen Teiler von zwei natürlichen Zahlen.
Algorithmus 1: Wechselwegnahme-Algorithmus
Algorithmus 2: Euklidischer Algorithmus
Der Euklidische Algorithmus basiert auf der gleichen Idee wie der Wechselwegnahme-Algorithmus. Nur wird hier die wiederholte Subtraktion der kleineren von der größeren Zahl durch die Berechnung des Rests bei der ganzzahligen Division ersetzt. Wenn man beispielsweise mit den beiden Zahlen x = 3642431875 und y = 15 beginnt, so liefert die Restberechnung 3642431875 % 15 den Wert 10. Genau diesen Wert erhält man ebenfalls, wenn man 242828791-mal die kleinere Zahl 15 von der größeren Zahl 3642431875 abzieht. Das heißt, dass 242828791 Subtraktionen durch eine Division mit Restberechnung ersetzt werden. Aus diesen Betrachtungen wird deutlich, dass der Euklidische Algorithmus schneller zum Ergebnis kommt als der Wechselwegnahme-Algorithmus.
Effizienz bei Algorithmen
Ziel beim algorithmischen Problemlösen ist es, Algorithmen zu entwickeln, die ein vorgegebenes Problem korrekt und möglichst effizient lösen.
Zwei Algorithmen heißen äquivalent, wenn sie bei gleichen Ausgangszuständen jeweils gleiche Endzustände erzeugen. Von zwei äquivalenten Algorithmen heißt der effizienter, der mit weniger Ressourcen (d.h. Rechenzeit oder Speicherplatz) auskommt.
Wir werden uns mit solchen Effizienzfragen immer wieder auseinander setzen. So werden wir im Kapitel Komplexität von Algorithmen und Problemen uns gezielt mit Aufwandanalysen auseinandersetzen.
