 Theta von ... |
|
|
n^{3} / 1000 - 1000 n^{2} - 100n + 3 = Theta(n^{3})
stimmt das?! Ich und diese verdammten Landausymbole ...
__________________
I'm 71% Megatron!
|
|
19.11.2007 23:18 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
Wenn dem so ist, dann findest du durch geschicktes Abschätzen die zwei Konstanten ![[latex]c_0, c_1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?c_0, c_1) , 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]](http://www.matheboard.de/latex2png/latex2png.php?c_0 \cdot n^{3} \leq \left| \frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3\right| \leq c_1 \cdot n^{3})
für alle ![[latex]n \geq n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n \geq n_0) gilt.
Bekommst du solche Abschätzungen hin?
|
|
|
20.11.2007 12:39 |
|
|
|
|
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!
__________________
I'm 71% Megatron!
|
|
|
20.11.2007 12:46 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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 ![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0) 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.
|
|
|
20.11.2007 12:55 |
|
|
|
|
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.
__________________
I'm 71% Megatron!
|
|
|
20.11.2007 13:39 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?n_0 \geq 1) genügend groß gewählt, so dass der Term n^{3} / 1000 - 1000 n^{2} - 100n + 3 für alle 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]](http://www.matheboard.de/latex2png/latex2png.php?\frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3 \leq \frac{n^{3}}{1000} = \frac{1}{1000} \cdot n^3)
Es folgt also mit ![[latex]c_1 := \frac{1}{1000}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?c_1 := \frac{1}{1000}) :
![[latex]\left| \frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3\right| \leq c_1 \cdot n^{3}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\left| \frac{n^{3}}{1000} - 1000 n^{2} - 100n + 3\right| \leq c_1 \cdot n^{3})
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.
|
|
|
20.11.2007 14:27 |
|
|
|
