Wachstum von mathematischen Funktionen

13.12.2013, 23:09

Demel789

Wachstum von mathematischen Funktionen

Hallo,

ich habe aufgetragen bekommen, zu bestimmen, ob $\begin{eqnarray*} f(n) = n^{\log n} \end{eqnarray*}$ in subquadratischer $\begin{eqnarray*} f(n) \in o(n^2) \end{eqnarray*}$ , polynomieller $\begin{eqnarray*} \exists k \in \mathbb{N} : f(n) \in \mathcal O(n^k) \end{eqnarray*}$ , exponentieller $\begin{eqnarray*} \exists k \in \mathbb{N} : f(n) \in \mathcal O(2^{n^k}) \end{eqnarray*}$ oder subexponentieller Zeit $\begin{eqnarray*} \forall c \in \mathbb{R}^+ : f(n) \in \mathcal O(2^{n^c}) \end{eqnarray*}$ läuft.

Mir fehlen im Moment etwas die Ansätze...

Subquadratisch wird es nicht sein, da $\begin{eqnarray*} n^{\log n} \end{eqnarray*}$ schon für bspw. n=1000 schneller wächst als n^2.

Polynomielle Zeit wohl auch nicht, da k ja konstant bleibt, der Exponent log(n) also irgendwann größer als k sein wird.

Auch subexponentiell fällt weg, denn wählt man c nur klein genug, überholt $\begin{eqnarray*} n^{\log n} \end{eqnarray*}$ die Funktion auch.

Damit bliebe nur noch exponentielles Wachstum übrig.

Angenommen das stimmt, gefällt mir der Gedanke, das über das Ausschlussverfahren rauszufinden, nicht gerade Big Laugh

Deswegen wollte ich fragen, ob ihr dafür evtl. Tipps habt?

Vielen dank im Voraus! smile

02.04.2014, 13:34

kkk-87

Auf diesen Beitrag antworten »

Hi,

nutze einfach die Definition der Landau-Symbole http://de.wikipedia.org/wiki/Landau-Symbole. (Tabelle in etwa der Hälfte des Artikels).

Überprüfe damit, ob deine Funktion die jeweilige Bedingung erfüllt.

Gruß

02.04.2014, 18:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Demel789
Auch subexponentiell fällt weg, denn wählt man c nur klein genug, überholt $\begin{eqnarray*} n^{\log n} \end{eqnarray*}$ die Funktion auch.

Sicher?

EDIT: Ich sehe gerade erst, dass der Thread über drei Monate alt ist. Dann rechne ich nicht ernsthaft mehr mit einer Antwort. smile

Neue Frage »

Antworten »

Wachstum von mathematischen Funktionen

Verwandte Themen