O Notation Insertion Sort < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:07 Di 14.10.2008 | | Autor: | Knievel |
| Aufgabe | Zeigen sie, das [mm] n^{2} - n \in [/mm] Ω [mm] \left(n^{2} \right) [/mm]
d.h. die Zeitkomplexität wächst mindestens automatisch
Hinweis: Wenden Sie die Definition der Menge Ω(f(n)) an und geben Sie c und n0 an.
Legen Sie Wert auf einen formal sauberen Beweis |
Moin moin
Hab jetzt schon zum Thema O Notation einiges im Netz gelesen aber ich komme noch nicht weiter mit dem Beweis.
Wir sollen ja zeigen, das es ein c > 0 und ein n0 gibt, so dass g(n) >= c * f(n)
Das ist aber nie der Fall, ausser ich nehme für c z.B. 0,1 an. Das macht für mich aber nicht wirklich Sinn, da die Konstante ja vernachlässigt werden soll und für die Analyse eigentlich keine Rolle spielen soll.
Wäre nett wenn mir jmd helfen könnte
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:09 Mi 15.10.2008 | | Autor: | bazzzty |
> Zeigen sie, das [mm]n^{2} - n \in[/mm] Ω [mm]\left(n^{2} \right)[/mm]
>
> d.h. die Zeitkomplexität wächst mindestens automatisch
Ich nehme an "quadratisch".
>
> Hinweis: Wenden Sie die Definition der Menge Ω(f(n))
> an und geben Sie c und n0 an.
>
> Legen Sie Wert auf einen formal sauberen Beweis
> Moin moin
>
> Hab jetzt schon zum Thema O Notation einiges im Netz
> gelesen aber ich komme noch nicht weiter mit dem Beweis.
> Wir sollen ja zeigen, das es ein c > 0 und ein n0 gibt,
> so dass g(n) >= c * f(n)
>
> Das ist aber nie der Fall, ausser ich nehme für c z.B. 0,1
> an. Das macht für mich aber nicht wirklich Sinn, da die
> Konstante ja vernachlässigt werden soll und für die Analyse
> eigentlich keine Rolle spielen soll.
Die Konstanten spielen keine Rolle mehr in der O-Notation, aber man muß eben zeigen, daß es solche Konstanten gibt.
Ich lasse Dir mal Deine Aufgabe und beweise etwas anderes, nämlich
[mm]n^2/10-2n\in\Omega(n^2)[/mm].
Wenn ich mir die beiden Funktionen anschaue, dann liegt [mm]n^2/10-2n[/mm] für alle Werte deutlich unter [mm][mm] n^2[/mm] [mm].
Was aber auffällt: Die [mm]2n[/mm] fallen für große [mm]n[/mm] immer weniger ins Gewicht (deshalb wählt man ein [mm]n_0[/mm]) und
die dominierenden Teile liegen nur um einen konstanten Faktor auseinander (daher dann das [mm][mm] c_0[/mm] [mm]). Bei beidem darf man ruhig großzügig sein. Ab [mm]n_0=100[/mm] ist [mm]n^2/10-2n>n^2/20[/mm] und [mm]20\cdot n^2/20\geq n^2[/mm].
|
|
|
|
