Informatiker Board | Druckvorschau: Erste Anfänge mit der O-Notation

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Erste Anfänge mit der O-Notation (http://www.informatikerboard.de/board/thread.php?threadid=2897)

Geschrieben von Shizmo am 05.03.2016 um 13:46:

Okay, also meine Sortierung würde dann so ausschauen:

$[latex]\sqrt{n}[/latex]$
$[latex]n \cdot log(log(2^n))[/latex]$
$[latex]n \cdot log(n)^2[/latex]$
$[latex]n \cdot log(log(n))[/latex]$
$[latex]n \cdot log(n)[/latex]$
$[latex]4^{log(n)}[/latex]$
$[latex]n^{1,5}[/latex]$
$[latex]2^{log(n)}[/latex]$
$[latex]\frac{2^{n+1}}{2}[/latex]$

Und bei den letzten 2 habe ich eine Konstante ( $[latex]\frac{1}{4}[/latex]$ ) rausbekommen, also eine $[latex]\Theta[/latex]$ -Äquivalenz.

Ich bin mir nur nicht ganz sicher, ist $[latex]n \cdot log(n)^2[/latex]$ das gleiche, wie Punk4 bei der Aufgabe auf dem Bild?

Geschrieben von eulerscheZahl am 05.03.2016 um 14:47:

Wir hatten uns doch schon darauf geeinigt, dass n langsamer wächst als n*log(n). Also muss es weiter nach oben (direkt nach sqrt(n)).
Dann schreiben wir die anderen mal ein wenig um:
$[latex]n \cdot \log(\log(2^n)) = n \cdot \log(n\cdot\log(2)) = n \cdot \log(n)[/latex]$
$[latex]n \cdot \log(n)^2 = n \cdot \log(n) \cdot \log(n)[/latex]$
Es gilt: $[latex]n \cdot \log(\log(n)) < n\cdot\log(n)=n \cdot \log(\log(2^n))<n \cdot \log(n)^2[/latex]$

$[latex]2^{\log(n)} = n[/latex]$ (für n > 0)
$[latex]4^{\log(n)} = 2^{2\cdot\log(n)} = (2^{\log(n)})^2 = n^2[/latex]$
Und $[latex]\frac{2^{n+1}}{2} = 2^n[/latex]$

Geschrieben von Shizmo am 05.03.2016 um 19:50:

Zitat:

Original von eulerscheZahl
Wir hatten uns doch schon darauf geeinigt, dass n langsamer wächst als n*log(n). Also muss es weiter nach oben (direkt nach sqrt(n)).

Natürlich, da hab ich wohl was durcheinander gebracht.

Zitat:

Dann schreiben wir die anderen mal ein wenig um:
$[latex]n \cdot \log(\log(2^n)) = n \cdot \log(n\cdot\log(2)) = n \cdot \log(n)[/latex]$
$[latex]n \cdot \log(n)^2 = n \cdot \log(n) \cdot \log(n)[/latex]$
Es gilt: $[latex]n \cdot \log(\log(n)) < n\cdot\log(n)=n \cdot \log(\log(2^n))<n \cdot \log(n)^2[/latex]$

$[latex]2^{\log(n)} = n[/latex]$ (für n > 0)
$[latex]4^{\log(n)} = 2^{2\cdot\log(n)} = (2^{\log(n)})^2 = n^2[/latex]$
Und $[latex]\frac{2^{n+1}}{2} = 2^n[/latex]$

Ahh, auf die Idee einfach mal Umzuformen bin ich nicht gekommen großes Grinsen

Vielen, vielen Dank.
Aber noch eine Frage, aber was anderes, du kennst dich ja sicher auch sehr gut mit LaTeX aus, wenn ich:

code:
1:	$\lim_{n \to \infty} \frac{42}{n} = 0$

schreibe, sollte doch eine schöne Limes Funktion kommen, allerdings ist bei mir das $[latex]n \to \infty[/latex]$ nicht unter dem lim, hast du eine Idee warum das so ist?

Der Codeabschnitt schaut so aus:

code:
1: 2:	\item Beispiel: $\lim_{n \to \infty} \frac{42}{n} = 0$\\\\ Also $42 = \mathcal{O}(n)$

Geschrieben von eulerscheZahl am 05.03.2016 um 20:56:

Sehr gut ist übertrieben. Aber bei der Bachelorarbeit hat es gute Dienste geleistet.
In LaTeX gibt es 2 Modi für Formeln: abgesetzt und inline.
Mit $$ schreibst du im inline Modus. Der ist darauf ausgelegt, nicht mehr Platz zu brauchen, als der Fließtext (ausgenommen Dinge wie underbrace).
Wenn du mit \begin{align*}...\end{align*} oder \[...\] arbeitest, geht der limes über 2 Zeilen.
Du kannst aber auch im inline Modus zweizeilig schreiben:

code:
1:	$\lim\limits_{\substack{n \to \infty}} \frac{42}{n} = 0$