Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Mastertheorem Aufwärts: Hauptseite Algorithmen Vorherige Seite: Inhalt   Inhalt

Unterabschnitte

Rekurrenzen

Euklid (Bestimmung des ggTs)

Der Euklidische Algortihmus berechnet den ggT mittels rekursiven Aufrufen1 folgendermaßen:

\begin{displaymath}ggT(x,y)=ggT(y,x\,\,mod\,\,y)\end{displaymath}

Hierbei werden alle Faktoren, die nicht Primfaktoren beider Zahlen sind, herausgezogen, bis letztendlich $ggT(\sum Primfaktoren,0)$ ü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}$ bestimmt, $F_{k-2}$ herauskommt, da $F_{k}=F_{k-1}+F_{k-2}$. Es müssen somit genau $k$ Schritte durchgeführt werden, um darauf zu kommen, daß der ggT zweier Fibonaccizahlen, die im Wort-Case aufeinander folgen, $1$ ist.
Für Fibonaccizahlen gilt

\begin{displaymath}F_{k}\geq (\frac{3}{2})^{k-1}\end{displaymath}

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})$.

Binäre Suche


\begin{displaymath}T(n)=\Biggl \{\begin {array}{ll} 0&f\uml {u}r\, n\leq 0\\ 1&... ...T(\lfloor\frac{n+1}{2}\rfloor-1)&f\uml {u}r\,n>1\\ \end{array}\end{displaymath}


\begin{displaymath}T(n)=1+T(\lfloor\frac{n+1}{2}\rfloor-1)\leq 1+T(\lfloor\frac{n}{2}\rfloor)\end{displaymath}

1.Fall: $n$ ist eine Zweierpotenz, etwa $2^{k}$
$T(n)$ $=T(2^{k})\leq 1+ T(\frac {2^k}{2})$
  $=1+T(2^{k-1})$
  $\leq 1+1+T(2^{k-2})=2+T(2^{k-2})$
  $\leq...\leq r+ T(2^{k-r})=_{r=k}k+T(2^{0})=k+1$
  $=log (n) +1 = O(log(n))$

2.Fall: $n$ beliebig: Sei $2^{k-1}<n<2^{k}$ $(\rightarrow k=\lceil log(n) \rceil)$
$T(n)\leq T(2^{k})\leq k+1=\lceil log(n) \rceil +1 = O (log(n))$

Mergesort

$T(1)=0$
$T(n)=n+T(\lfloor\frac{n+1}{2}\rfloor)+T(n-\lfloor\frac{n+1}{2}\rfloor)\leq n+2*T(\lfloor\frac{n+1}{2}\rfloor)\approx n+2*T(\lfloor\frac{n}{2}\rfloor)$

1. Fall $n=2^{k}$:
$T(2^{k})$ $=2^{k}+2T(\frac{2^{k}}{2})$
  $=2^{k}+2T(2^{k-1})$
  $\leq 2^{k}+2(2^{k-1}+2T(2^{k-2})$
  $\leq 2*2^{k}+2^{2}T(2^{k-2})$
  $\leq...\leq r*2^{k}+2^{r}*T(0)$
  $=r*2^{k}$
  $=_{r=k}k*2^{k}$
$\Rightarrow$ $O(log(n)*n)$

Quicksort

Worst-Case


\begin{displaymath}T(n)=(n-1)+\begin{array}{l}max \\ 1\leq i \leq n\end{array}(T(n-i)+T(i-1))=n-1+T(n-1)+T(0)\end{displaymath}


\begin{displaymath}=n-1+n-2+n-3+...+n-n=\sum_{k=1}^{k=n}(n-k)\end{displaymath}

$\Rightarrow O(n^{2})$

Average Case

Für $n\geq 2$:

\begin{displaymath}T(n)=n-1+\frac{1}{n}\sum^{n}_{i=1}(T(n-i)+T(i-1))=n-1+\frac{2}{n}\sum^{n}_{i=1}T(i-1)\end{displaymath}

Durch Induktion kann man zeigen (ohne Beweis):

\begin{displaymath}T(n)=2(n+1)H(n)-4n\end{displaymath}

Wobei $H(n)$ die harmonsische Reihe ist, für die gilt:

\begin{displaymath}\int_{1}^{n+1}\frac{1}{x}dx\leq\sum^{n}_{i=1}\frac{1}{i}\leq\int^{n+1}_{2}\frac{1}{x-1}dx+1\end{displaymath}

Hiermit läßt sich $H(n)$ nach $log(n+1)$ bzw. $log(n)+1$ abschätzen. Somit ist die Laufzeit im Average Case:

\begin{displaymath}\Rightarrow\Theta(n log (n))\end{displaymath}


Fußnoten

... Aufrufen1
Es gibt auch ein iteratives Verfahren des Euklidischen Algorithmusses.
next up previous contents
Nächste Seite: Mastertheorem Aufwärts: Hauptseite Algorithmen Vorherige Seite: Inhalt   Inhalt