Kurs:Algorithmen und Datenstrukturen/Vorlesung/GGT Vergleich

Aus Wikiversity
Zur Navigation springen Zur Suche springen




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.


Vorheriges Thema.jpg Discussion Nächstes Kapitel .jpg