Theta von ...

19.11.2007, 23:18	Auf diesen Beitrag antworten »
JROppenheimer	Theta von ... n^{3} / 1000 - 1000 n^{2} - 100n + 3 = Theta(n^{3}) stimmt das?! Ich und diese verdammten Landausymbole ...


20.11.2007, 12:39	Auf diesen Beitrag antworten »
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?
20.11.2007, 12:46	Auf diesen Beitrag antworten »
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!
20.11.2007, 12:55	Auf diesen Beitrag antworten »
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.
Anzeige

20.11.2007, 13:39	Auf diesen Beitrag antworten »
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.
20.11.2007, 14:27	Auf diesen Beitrag antworten »
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.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »