Laufzeitanalyse < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Leute,
Man soll für folgenden Algorithmus eine Laufzeit-Analyse durchführen. Vielleicht hat ja jemand eine Idee. Es seien im Folgenden $x [mm] \in \IR$ [/mm] und $n [mm] \in \IN_0$:
[/mm]
[mm]
\begin{array}{l}
\mathrm{hoch}\left(x,n\right):\\
\quad \textrm{if} \left(n = 0\right):\\
\quad \quad \textrm{return}\,\,1\\
\quad \textrm{if}\left(n \bmod 2 = 1\right):\\
\quad \quad \textrm{return}\,\,\mathrm{hoch}\left(x,n-1\right)\cdot x\\
\quad \textrm{else}:\\
\quad \quad \mathrm{faktor} = \mathrm{hoch}\left(x,\frac{n}{2}\right)\\
\quad \quad \textrm{return}\,\,\mathrm{faktor}\cdot\mathrm{faktor}
\end{array}
[/mm]
Zu zeigen ist, daß die Berechnung von [mm] $x^n$ [/mm] mit der binären (also der obigen) Methode höchstens [mm] $2\left\lceil \log n \right\rceil$ [/mm] Multiplikationen erfordert. Ich habe mir überlegt, daß der obige Algorithmus folgender Rekurrenzrelation gehorcht:
[mm]
\begin{array}{l}
T\left(0\right) = 1\\
T\left(n\right) =
\begin{cases}
T\left(n-1\right), & \textrm{wenn}\ n \bmod 2 = 1\\
T\left(\frac{n}{2}\right), & \textrm{sonst}
\end{cases}
\end{array}
[/mm]
Jetzt könnte man es mit Induktion versuchen. Aber wie soll ich hier anfangen? Für $n = 0$ ist ja [mm] $2\log [/mm] 0$ nicht definiert. Für $n = 1$ erhalte ich [mm] $2\log [/mm] 1 = 0 [mm] \ne T\left(1\right) [/mm] = [mm] T\left(0\right) [/mm] = 1$.
Hat jemand eine Idee wie hier vorzugehen ist?
Danke!
Grüße
Karl
[P.S. Ich stelle die Frage auch im Usenet und setze den Google-Link dorthin, sobald er existiert.
EDIT: Er ![[]](/images/popup.gif) existiert jetzt.]
|
|
|
