Informatiker Board | Druckvorschau: Theta von ...

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Theta von ... (http://www.informatikerboard.de/board/thread.php?threadid=314)

Geschrieben von JROppenheimer am 19.11.2007 um 23:18:

Theta von ...

n^{3} / 1000 - 1000 n^{2} - 100n + 3 = Theta(n^{3})

stimmt das?! Ich und diese verdammten Landausymbole ...

Geschrieben von Tobias am 20.11.2007 um 12:39:

Wenn dem so ist, dann findest du durch geschicktes Abschätzen die zwei Konstanten [latex]c_0, c_1[/latex]

, 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?

Geschrieben von JROppenheimer am 20.11.2007 um 12:46:

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!

Geschrieben von Tobias am 20.11.2007 um 12:55:

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]

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.

Geschrieben von JROppenheimer am 20.11.2007 um 13:39:

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.

Geschrieben von Tobias am 20.11.2007 um 14:27:

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.