Unterabschnitte
Der Euklidische Algortihmus berechnet den ggT mittels rekursiven Aufrufen
1 folgendermaßen:
Hierbei werden alle Faktoren, die nicht Primfaktoren beider Zahlen sind, herausgezogen, bis letztendlich
![$ggT(\sum Primfaktoren,0)$](img2.png)
übrigbleibt.
Der
Worst-Case-Fall des Euklidalgorithmus sind die Fibonaccizahlen. Die Fibonaccizahlen haben die Eigenschaft, daß wenn man den Rest von
![$F_{k}/F_{k-1}$](img3.png)
bestimmt,
![$F_{k-2}$](img4.png)
herauskommt, da
![$F_{k}=F_{k-1}+F_{k-2}$](img5.png)
. Es müssen somit genau
![$k$](img6.png)
Schritte durchgeführt werden, um darauf zu kommen, daß der ggT zweier Fibonaccizahlen, die im Wort-Case aufeinander folgen,
![$1$](img7.png)
ist.
Für Fibonaccizahlen gilt
Wir sehen, daß je größer die Zahlen werden, die Häufigkeit der Fibonaccizahlen logarithmisch abnimmt, da die Größe der Fibonaccizahlen exponentiell steigt. Somit gilt
![$O(\log{n})$](img9.png)
.
1.Fall:
![$n$](img12.png)
ist eine Zweierpotenz, etwa
2.Fall:
![$n$](img12.png)
beliebig: Sei
1. Fall
![$n=2^{k}$](img25.png)
:
Für
![$n\geq 2$](img39.png)
:
Durch Induktion kann man zeigen (ohne Beweis):
Wobei
![$H(n)$](img42.png)
die harmonsische Reihe ist, für die gilt:
Hiermit läßt sich
![$H(n)$](img42.png)
nach
![$log(n+1)$](img44.png)
bzw.
![$log(n)+1$](img45.png)
abschätzen. Somit ist die Laufzeit im Average Case:
Fußnoten
- ... Aufrufen1
- Es gibt auch ein iteratives Verfahren des Euklidischen Algorithmusses.