Informatiker Board | Theoretische Informatik | Erste Anfänge mit der O-Notation

Informatiker Board » Themengebiete » Theoretische Informatik » Erste Anfänge mit der O-Notation

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): « vorherige 1 [2]

Erste Anfänge mit der O-Notation

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Zitatantwort auf diesen Beitrag erstellen

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?

05.03.2016 13:46

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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]$

__________________
Syntax Highlighting fürs Board (Link)

05.03.2016 14:47

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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)$

Shizmo hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shizmo: 05.03.2016 19:50.

05.03.2016 19:50

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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$

__________________
Syntax Highlighting fürs Board (Link)

05.03.2016 20:56

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Perfekt, vielen, vielen Dank für deine Hilfe!!!!!! Daumen hoch

06.03.2016 10:25

Seiten (2): « vorherige 1 [2]

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Erste Anfänge mit der O-Notation