Laufzeitkomplexität mit Reduktionsfaktor

27.07.2015, 09:59	melianarana	Auf diesen Beitrag antworten »
Laufzeitkomplexität mit Reduktionsfaktor Hallo, ich hab hier einen Prozess, der bei einer Zahl $\begin{eqnarray} O(n) \end{eqnarray}$ anfängt und in jedem Schritt mindestens um den Faktor $\begin{eqnarray} \Omega (1/n^9) \end{eqnarray}$ reduziert wird, dh $\begin{eqnarray} X_{t+1} \leq X_t (1-r) \end{eqnarray}$ mit $\begin{eqnarray} X_0 \in O(n) \end{eqnarray}$ und $\begin{eqnarray} r \in \Omega (\frac{1}{n^9} ) \end{eqnarray}$ . Nun möchte ich zeigen, dass ich in $\begin{eqnarray} O (n^9 \ln (n)) \end{eqnarray}$ Schritten $\begin{eqnarray} X_t \leq c \cdot \sqrt{\alpha \ln (n)} \end{eqnarray}$ erreiche, mit $\begin{eqnarray} \alpha \in \Omega (n^{-5/2}) \end{eqnarray}$ und $\begin{eqnarray} c \geq 0,15 \end{eqnarray}$ ist eine Konstante. Meine Frage ist: gibt es für eine solche Situation eine gut anwendbare Formel und wo finde ich sie? Danke schonmal!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »