Kurs:Algorithmen und Datenstrukturen/Vorlesung/GGT Vergleich
ggT: Funktional vs. Imperativ
BearbeitenIn diesem Kapitel werden wir den funktionalen Algorithmus des größten gemeinsamen Teilers mit dem imperativen Algorithmus vergleichen.
Version 1
BearbeitenGGT1 var X,Y: int;
input X,Y;
while X ≠ Y {
while X > Y { X := X-Y; }
while X < Y { Y := Y-X; }
}
output X;
Die Auswertung für X=19 und Y=5 lautet:
| X | Y |
| 19 | 5 |
| 14 | 5 |
| 9 | 5 |
| 4 | 5 |
| 4 | 1 |
| 3 | 1 |
| 2 | 1 |
| 1 | 1 |
Die Berechnung erfolgt durch die Subtraktion der jeweils kleineren Zahl. Es ist zu Beobachten, dass der ggT mittels Subtraktion nicht effizient berechnet werden kann.
Version 2
BearbeitenGGT2 var X,Y,R: int;
input X,Y;
R := 1
while R ≠ 0 {
R := X % Y; X := Y; Y := R;
}
output X;
Die Auswertung für X=19 und Y=5 lautet:
| X | Y | R |
| 19 | 5 | 1 |
| 5 | 4 | 4 |
| 4 | 1 | 1 |
| 1 | 0 | 0 |
Die Auswertung für X=2 und Y=1000 lautet:
| X | Y | R |
| 2 | 1000 | 2 |
| 2 | 0 | 0 |
Die Berechnung erfolgt hier durch die Modulo Funktion. Falls X<Y sein sollte, werden X und Y erst vertauscht, wie in der zweiten Auswertung.
Dieser Algorithmus ist folgendermaßen definiert:
![{\displaystyle [\![GGT2]\!](x,y)=\left\{{\begin{array}{ll}ggT(x,y)&falls~x,y>0\\y&falls~x=y~\neq 0~oder~x=0,y\neq 0\\\bot &falls~y=0\\ggT(|x|,|y|)&falls~x<0~und~y>0\\-ggT(|x|,|y|)&falls~y<0\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dfc63094c84553002602a77d610d7c8edd86895)
Vergleich
BearbeitenIntuitiv ist GGT2 schneller als GGT1, was man durch die Komplexität von Algorithmen zeigen kann.
Literatur
BearbeitenDa die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.3.3 zu finden.
