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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge

Shizmo

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

eulerscheZahl

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$

Shizmo

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:

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

Shizmo

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?

Shizmo

Haha

Ja soweit habe ich nicht nach vorne geschaut großes Grinsen

eulerscheZahl

Alles eine Frage der Betrachtungsweise smile

Schau mal auf die Achsenbeschriftung.

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

Shizmo

Ok vielen Dank, werde das gleich mal durchprobieren.

Hab mir grad gedacht ich hau alles in einen Plotter und schaus mir da an, ist aber gar nicht so leicht, die alle zu vergleichen großes Grinsen

Aber nochwas was ich nicht verstehe: (siehe Grafik)

Dass x*log(x) schneller steigt als x macht für mich sinn, aber warum steigt x*log(log(x)) weniger schnell als x???

x*log(x)
x
x*log(log(x))

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

eulerscheZahl

Wenn du das nach Definition zeigen willst, musst du wohl in den sauren Apfel beißen.

Letzendlich ist das aber eine Grenzwertberechnung: welche Funktion wächst im Unendlichen schneller.
$[latex]f(x) = n,\, g(x) = \sqrt n[/latex]$
$[latex]\lim_{x\to\infty} = \frac{f(x)}{g(x)} = \infty[/latex]$ heißt, dass f schneller wächst als g, daher ist $[latex]g(x) = \mathcal{O}(f(x))[/latex]$ .
Berechnest du den Grenzwert von g(x)/f(x), ist das Ergebnis 0, was heißt g wächst langsamer als f.
Kriegst du eine echt positive Konstante, sind sie in der $[latex]\Theta[/latex]$ Notation äquivalent.

Shizmo

Okay passt, wenn ich jetzt aber alles so durchrechne und vergleiche, bin ich ewig dabei, wie finde ich das schneller raus?

Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.