Komplexität

13.07.2011, 17:45	MatheMathosi	Auf diesen Beitrag antworten »
Komplexität Meine Frage: Hier meine Aufgabe: Sort the functions $\begin{eqnarray} <br /> n^2, \sqrt{n}, n!,n^n,n<br /> \end{eqnarray}$ Reminder : $\begin{eqnarray} f \in o(g) \ : \ \exists c > 0 \ \exists n_{0} \in \mathbb{N} \ \forall n \geq n_{0} \ : \ 0 \leq f(n) < c \cdot g(n) \end{eqnarray}$ Solutions 1. $\begin{eqnarray} \sqrt{n} \in o(n) \ , n_{0} =\lceil\sqrt{\frac{1}{c}}\rceil \end{eqnarray}$ 2. $\begin{eqnarray} n \in o(n^2) \ , n_{0} = \lceil\frac{1}{c}\rceil \end{eqnarray}$ 3. $\begin{eqnarray} n! \in o(n^n) \ , n_{0} = \lceil\frac{1}{c}\rceil \end{eqnarray}$ Meine Ideen: Also mir ist nicht ganz schlüssig wie die Lösungen hier entstanden sind bei 2. komme ich darauf aber bei 1. komme ich nicht darauf. Mein Ansatz : $\begin{eqnarray} \sqrt{n} \leq c \cdot n \Leftrightarrow \frac{\sqrt{n}}{c} \leq n \Leftrightarrow \frac{1}{c} \leq \sqrt{n} \Leftrightarrow \frac{1}{c^2} \leq n <br /> \end{eqnarray}$ ???
15.07.2011, 17:38	MatheMathosi	Auf diesen Beitrag antworten »
Hat sich erledigt die ertse Musterlösung ist falsch. Mein Ansatz ist somit korrekt wobei $\begin{eqnarray} n > \frac {1}{c^2} \end{eqnarray}$ sein muss.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »