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 für alle 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 genügend groß gewählt, so dass der Term n^{3} / 1000 - 1000 n^{2} - 100n + 3 für alle positiv ist. Dann gilt: Es folgt also mit : 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 » |