O-Notation < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:32 Di 15.01.2013 | | Autor: | bandchef |
| Aufgabe | | Kein konkrete Aufgabe. |
Hi Leute!
Wenn ich nach einer Betrachtung durch das Master-Theorem sowas stehen haben wie bspw
$n [mm] \cdot [/mm] log(n) [mm] \in O\left( n^{log_2(3) - \epsilon} \right)$ [/mm] mit passendem [mm] $\epsilon [/mm] > 0$
dann weiß ich nie ob nun $n [mm] \cdot [/mm] log(n)$ darin enthalten ist oder nicht. Meiner Ansicht nach nicht, weil das $n$ durch den multiplikativen Anteil $log(n)$ wesentlich kleiner wächst als die obere Grenze O, auch wenn ich mit einem passenden [mm] $\epsilon \approx [/mm] 0,585$ auf [mm] $n^1$ [/mm] kommen würde. Da das O-Kalkül ja nur die höchste Potenz betrachtet, wäre es ja doch darin enthalten, oder?
Laut meiner Lösung gilt aber: $n [mm] \cdot [/mm] log(n) [mm] \notin O\left( n^{log_2(3) - \epsilon} \right)$ [/mm] mit passendem [mm] $\epsilon [/mm] > 0$
Gibt es da nun eine Vorgehensweise wie man das besser erkennen kann? Oder wie ich denke, damit ich solche Fälle erkenne?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:05 Di 15.01.2013 | | Autor: | Helbig |
Hallo bandchef,
> Wenn ich nach einer Betrachtung durch das Master-Theorem
> sowas stehen haben wie bspw
>
> [mm]n \cdot log(n) \in O\left( n^{log_2(3) - \epsilon} \right)[/mm]
> mit passendem [mm]\epsilon > 0[/mm]
>
> dann weiß ich nie ob nun [mm]n \cdot log(n)[/mm] darin enthalten
> ist oder nicht. Meiner Ansicht nach nicht, weil das [mm]n[/mm] durch
> den multiplikativen Anteil [mm]log(n)[/mm] wesentlich kleiner
> wächst als die obere Grenze O, auch wenn ich mit einem
> passenden [mm]\epsilon \approx 0,585[/mm] auf [mm]n^1[/mm] kommen würde. Da
> das O-Kalkül ja nur die höchste Potenz betrachtet, wäre
> es ja doch darin enthalten, oder?
Halte Dich lieber an die Definition. Ich stelle mir gerade vor, wie das O-Kalkül die Potenz betrachtet 
>
> Laut meiner Lösung gilt aber: [mm]n \cdot log(n) \notin O\left( n^{log_2(3) - \epsilon} \right)[/mm]
> mit passendem [mm]\epsilon > 0[/mm]
Das hängt von Deinem "passenden" [mm] $\epsilon$ [/mm] ab!
Setzen wir mal [mm] $\alpha [/mm] = [mm] \log_2 [/mm] 3 - [mm] \epsilon\,,$ [/mm] um die Formeln etwas übersichtlicher zu machen.
Dann haben wir:
[mm] $n\log [/mm] n [mm] \in O(n^\alpha)\quad\gdw\quad \limsup {n\log n \over n^\alpha} [/mm] < [mm] \infty \quad\gdw\quad \lim {\log n \over n^{\alpha - 1} }< \infty\,.$
[/mm]
Nun wissen wir aus der Analysis, daß letzteres genau dann der Fall ist, wenn [mm] $\alpha [/mm] - 1 > 0$ ist, bzw. wenn [mm] $\epsilon [/mm] < [mm] \log_2 [/mm] 3 - 1$ ist. Wegen [mm] $\log_2 [/mm] 3 > 1$ gibt es so ein positives [mm] $\epsilon\,.$ [/mm] Wenn Du allerdings [mm] $\epsilon [/mm] = [mm] \log_2 [/mm] 3 - 1$ setzt, ist [mm] $\alpha [/mm] = 1$, und [mm] $n\log [/mm] n [mm] \notin O(n^{\log_2 3 - \epsilon})\,.$
[/mm]
>
> Gibt es da nun eine Vorgehensweise wie man das besser
> erkennen kann? Oder wie ich denke, damit ich solche Fälle
> erkenne?
Ja. Schlicht nach Definition argumentieren und Dein Wissen aus der Ana1 anwenden.
Gruß,
Wolfgang
|
|
|
|
