komplexitätsanalyse

17.02.2011, 19:29

stud-ente

komplexitätsanalyse

so eine frage beschäftigt mich heute abend noch:

und zwar geht es um eine komplexitätsanalyse..
ich habe

$\begin{eqnarray*} F(n)=\sum\limits_{k=0}^{n-1} \frac{k}{(k+1)*(k+2)} + \frac{2*n}{n+1} \end{eqnarray*}$

und zwar soll ich zeigen, dass diese rekursion $\begin{eqnarray*} O(n*log(n)) \end{eqnarray*}$ zeit benötigt.

meine idee war:

$\begin{eqnarray*} F(n)=\sum\limits_{k=0}^{n-1} \frac{k}{(k+1)*(k+2)} + \frac{2*n}{n+1} \end{eqnarray*}$
und
$\begin{eqnarray*} F(n+1)=\sum\limits_{k=0}^{n} \frac{k}{(k+1)*(k+2)} + \frac{2*n+2}{n+2} \end{eqnarray*}$

diese beiden subtrahieren und komme dann auf:
$\begin{eqnarray*} F(n+1)=\frac{n+2}{(n+1)*(n+2)} + F(n) \end{eqnarray*}$

nur wenn ich mir den ausdruck ansehe:
$\begin{eqnarray*} \frac{n+2}{(n+1)*(n+2)} \end{eqnarray*}$

dann verhält sich das ja wie $\begin{eqnarray*} \frac{1}{n} \end{eqnarray*}$ und das verhält sich ja wieder wie $\begin{eqnarray*} O(log(n)) \end{eqnarray*}$ .. was ja nicht ganz stimmt, mit dem was ich zeigen soll.

hmmm... verwirrt

20.02.2011, 23:31

Abakus

Auf diesen Beitrag antworten »

RE: komplexitätsanalyse

Zitat:

Original von stud-ente
so eine frage beschäftigt mich heute abend noch:

und zwar geht es um eine komplexitätsanalyse..
ich habe

$\begin{eqnarray*} F(n)=\sum\limits_{k=0}^{n-1} \frac{k}{(k+1)*(k+2)} + \frac{2*n}{n+1} \end{eqnarray*}$

und zwar soll ich zeigen, dass diese rekursion $\begin{eqnarray*} O(n*log(n)) \end{eqnarray*}$ zeit benötigt.

Hallo,

nein, das ist keine Rekursion: du hast eine Funktion mit n als Variable.

Eine Idee ist hier Partialbruchzerlegung erstmal.

Grüße Abakus smile

Neue Frage »

Antworten »

komplexitätsanalyse

Verwandte Themen