Kurs:Algorithmen und Datenstrukturen/Vorlesung/GGT Vergleich




ggT: Funktional vs. Imperativ Bearbeiten

In diesem Kapitel werden wir den funktionalen Algorithmus des größten gemeinsamen Teilers mit dem imperativen Algorithmus vergleichen.

Version 1 Bearbeiten

GGT1 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 Bearbeiten

GGT2 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:

 

Vergleich Bearbeiten

Intuitiv ist GGT2 schneller als GGT1, was man durch die Komplexität von Algorithmen zeigen kann.

Literatur Bearbeiten

Da 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.