Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Frage zu Groß-Omega

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Frage zu Groß-Omega » 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 7 Beiträge
eulerscheZahl	Kann man so machen. Aber letztendlich läuft es auch wieder darauf hinaus, dass man zuerst das c wählt, dann das n.
Shizmo	Also mein Prof hat auch gesagt, dass man immer wieder ein kleineres c finden kann (so wie mein vorletzter Beitrag). Seine Lösung war dann so: $[latex]c_1 \cdot 5n\cdot log(n) \leq 10n+5 \equiv c_1 \cdot n \cdot log(n) \leq 2n+1[/latex]$ dann hat er abgeschätzt: $[latex]\leq 3\cdot n[/latex]$ $[latex]\Rightarrow c_1 \cdot n\cdot log(n) \leq 3\cdot n \equiv c_1 \cdot log(n) \leq 3[/latex]$ Widerspruch
Shizmo	Ok, ok, dann nehm ich das mal so hin. Vielen Dank!!
eulerscheZahl	Du wählst aber erst das c. Und dann findest du ein passendes n.
Shizmo	Hmm ja theoretisch versteh ich das eigentlich, aber ich wähl ein c: =1 und n = 8 $[latex]1 \cdot 120 \leq 85[/latex]$ okay das passt, aber ich kanns ja auch immer so wählen dass es nicht passt bsp c=0.5 und n=8 Also ich mein damit, ich find immer ein c wo es passt, und ein c wo es nicht passt. Also kann ich ja nie was zeigen, da ich mir immer wieder selbst widersprechen kann.
eulerscheZahl	Und wenn du dann das n wählst, findest du eins, das die Ungleichung nicht mehr erfüllt. Und da das c zuerst gewählt wird, kann im Anschluss immer ein solches n gefunden werden. $[latex]\lim_{n \to \infty}\log(n) = \infty[/latex]$ . Daran kannst du mit einem Konstanten Faktor nichts ändern.
Shizmo	Frage zu Groß-Omega Hallo $[latex]f(n):= 5n \cdot log(n) \,\,\,\, g(n) := 10n+5[/latex]$ Eigentlich soll ich zeigen $[latex]g \not\in \Theta(f)[/latex]$ Ich hab mir gedacht ich teils auf, ich zeige dass es entweder nicht in Groß-O oder nicht in Groß-Omega ist, in Groß-O ist es, das ist nicht schwer zu zeigen, aber wie zeige ich am einfachsten, dass es nicht in Groß-Omega ist. $[latex]c_1 \cdot 5n\cdot log(n) \leq 10n+5[/latex]$ Vor allem er will: $[latex]c_1 \in \mathbb{R^+}[/latex]$ Wenn ich jetzt ewig rumprobiere find ich trotzdem immer wieder eine Konstante (eine sehr kleine Konstante zB 0.000000000000000000000000000000000000000000000001) und dann ist der linke Teil wieder kleiner. LG