Aloha :)
Der Euklidische Algorithmus lässt sich z.B. in C wie folgt formulieren:
long ggT( long n, long m ) { return m=0 ? n : ggT(m, n%m); }
Bei benachbarten teilerfremden Zahlen erwarten wir daher die meisten Schritte. Die längste Folge benachbarter teilerfremder Zahlen ist die Fibonacci-Foge. Daher stellen \(2\) direkt aufeinaderfolgende Fibonacci-Zahlen den schlechtesten Fall dar. In jedem Schritt reduziert der Algorithmus den Index der Finbonacci-Zahlen um \(1\).
Für die \(k\)-te Fibonacci-Zahl \(F_k\) gibt es einen geschlossenen Ausdruck:$$F_k=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^k-\left(\frac{1-\sqrt5}{2}\right)^k\right]$$Daraus können wir bei einer gegebenen Fibonacci-Zahl \(F_k\) deren Index \(k\) und damit die Anzahl der Schritte des Euklid-Algorithmus abschätzen. Dazu überlegen wir uns, dass die hintere Klammer$$\left(\frac{1-\sqrt5}{2}\right)^k=(-0,618)^k\;\to\;0\quad\text{für }k\to\infty$$sehr schnell gegen Null konvergiert und daher vernachlässigbar ist. Damit bleibt in guter Näherung:
$$\left.F_k=\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^k\quad\right|\quad\cdot\sqrt5$$$$\left.\sqrt5\,F_k=\left(\frac{1+\sqrt5}{2}\right)^k\quad\right|\quad\ln(\cdots)$$$$\left.\ln(\sqrt5)+\ln(F_k)=k\,\ln\left(\frac{1+\sqrt5}{2}\right)\quad\right|\quad:\,\ln\left(\frac{1+\sqrt5}{2}\right)$$$$k=\frac{\ln(\sqrt5)+\ln(F_k)}{\ln\left(\frac{1+\sqrt5}{2}\right)}=1,6723+\frac{\ln(F_k)}{0,4812}=1,6723+2,08\,\ln(F_k)\approx2\,\ln(F_k)$$Für ein gegebenes Zahlenpaar \((n,m)\) können wir als Worst-Case-Abschätzung das Maximum zwischen zwei benachbarten Fibonacci-Zahlen einschließen:$$F_{k-1}\le\operatorname{max}(n,m)<F_k$$und erhalten so als worst-case-Abschätzung für die Anzahl der Schritte des Euklid-Algorithmus:$$T_{\text{max}}(n,m)\approx2\,\ln(\,\operatorname{max}(n,m)\,)$$
