Informatiker Board | Theoretische Informatik | Theta von ...

Informatiker Board » Themengebiete » Theoretische Informatik » Theta von ... » 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 6 Beiträge
Tobias	Nein, die Konstanten müssen konstant sein, d.h. sie dürfen nicht von n abhängen. Für die obere Schranke (das ist der einfache Fall) zeige ich dir mal einen möglichen Beweis: Es sei $[latex]n_0 \geq 1[/latex]$ genügend groß gewählt, so dass der Term n^{3} / 1000 - 1000 n^{2} - 100n + 3 für alle $[latex]n \geq n_0[/latex]$ positiv ist. Dann gilt: $[latex]\frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3 \leq \frac{n^{3}}{1000} = \frac{1}{1000} \cdot n^3[/latex]$ Es folgt also mit $[latex]c_1 := \frac{1}{1000}[/latex]$ : $[latex]\left\| \frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3\right\| \leq c_1 \cdot n^{3}[/latex]$ Die Idee hier ist, die Subtraktion - 1000 n^{2} - 100n + 3 wegzulassen und somit den Term nach oben abzuschätzen. Für n >= 1 fällt die +3 am Ende nicht mehr ins Gewicht, das z.B. 100n > 3, weswegen man sie auch direkt weglassen kann.
JROppenheimer	kann ich nich einfach hergehen und c0 abhängig von n machen? es muss ja gelten c0 * n^3 < n^3/1000 - 100n^2 - 100n +3 \| *1/n^3 da n eine ganze Zahl ist, muss hier auch keine Fallunterscheidung gemacht werden, oder? damit hätte man ja einfach eine Konstante c0 < 1/1000 - 100/n - 100/n^2 + 3/n^3 war so ein gedanke... für c1 kann man das ja dann analog lösen.
Tobias	Ja, das könnte hinkommen. 1.) Man betrachtet nicht die Funktionen sondern die Beträge der Funktionen (siehe Definition von Theta) 2.) Die Abschätzung muss erst für alle n ab einem bestimmten gelten. Was davor war, interessiert nicht. Du kannst also sagen: Diese Konstanten sind erst ab n > 10000000 gültig und verletzt trotzdem die Definition von Theta nicht. Was ich noch vermisse ist ein Beweis, dass deine Konstanten tatsächlich halten.
JROppenheimer	Soweit ich weiss, müssen c0 und c1 nur aus R+ sein, oder? n ist ja ganzzahlig, wenn ich mich hich irre. der kleinste wert von n ist 1. dann ist das ganze T(1) = 1/1000-1000-100+3 aber damit wäre die Laufzeit negativ, oder?! hier ist doch irgendwo ein denkfehler ... nur an der Formel orientierr, hätte ich gesagt, dass zB c0 = 1/10000 c1 = 3 könnte das hinkommen? Aber sicher bin ich mir da wirklich nich, gerade, wegen dem oben genannten!
Tobias	Wenn dem so ist, dann findest du durch geschicktes Abschätzen die zwei Konstanten , die gewährleisten, dass $[latex]c_0 \cdot n^{3} \leq \left\| \frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3\right\| \leq c_1 \cdot n^{3}[/latex]$ für alle $[latex]n \geq n_0[/latex]$ gilt. Bekommst du solche Abschätzungen hin?
JROppenheimer	Theta von ... n^{3} / 1000 - 1000 n^{2} - 100n + 3 = Theta(n^{3}) stimmt das?! Ich und diese verdammten Landausymbole ...