Laufzeit

01.11.2006, 18:46	donkarabelas	Auf diesen Beitrag antworten »
Laufzeit Hi! Hab einen algorithmus gegeben der folgende laufzeit-rekursion erfüllt: $\begin{eqnarray} T(n)~=~T(\lfloor \sqrt{n} \rfloor)+1 \end{eqnarray}$ Meine frage lautet: wie kann ich hier eine obere Schranke finden? durch iteratives einsetzen komm ich jedenfalls nicht weiter. Meine vermutung wäre ja das hier ein $\begin{eqnarray} O(n) \end{eqnarray}$ herauskommt. lg elias
01.11.2006, 19:18	papahuhn	Auf diesen Beitrag antworten »
RE: Laufzeit Für $\begin{eqnarray} n = 2^{2^i}, i \in \mathbb N \end{eqnarray}$ ergibt sich $\begin{eqnarray} T(n) = \operatorname{log}_2(\operatorname{log}_2(n)) + T(1) \end{eqnarray}$ . Wenn du nachweisen könntest, dass T monoton steigend ist, ließe sich $\begin{eqnarray} T(n) \leq T(m) \end{eqnarray}$ abschätzen mit $\begin{eqnarray} m = \min\{i \in \mathbb N \| 2^{2^i} \geq n\} \end{eqnarray}$ .
01.11.2006, 19:31	AD	Auf diesen Beitrag antworten »
RE: Laufzeit @papahuhn Da ist eine kleine Ungenauigkeit, die aber die Idee in keinster Weise beeinträchtigt: Für dein $\begin{eqnarray} n = 2^{2^i} \end{eqnarray}$ ist $\begin{eqnarray} T(n) = \log_2(\log_2(n)) + T(2) = \log_2(\log_2(n)) + 1+T(1) \end{eqnarray}$ .
01.11.2006, 19:38	papahuhn	Auf diesen Beitrag antworten »
RE: Laufzeit Jetzt fall ich aber aus allen Wolken.
01.11.2006, 19:42	AD	Auf diesen Beitrag antworten »
Glaub ich gern.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »