O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen Sie, dass [mm] $\mathcal{O}(f) [/mm] = [mm] \bigcup_{g\in\mathcal{O}(f)}^{}\mathcal{O}(g)$.
[/mm]
Zur Erinnerung: Für zwei Funktionen $f,g : [mm] \mathbb{N} \rightarrow \mathbb{N}$ [/mm] schreiben wir [mm] $f\in\mathcal{O}(g)$, [/mm] falls
[mm] $\exists [/mm] c > 0, [mm] \exists n_0 [/mm] > [mm] 0\forall [/mm] n [mm] \geq n_0 [/mm] : f(n) [mm] \leq [/mm] c [mm] \cdot [/mm] g(n)$. |
Folgendes glaube ich verstanden zu haben:
Damit die Aussage der Aufgabe stimmt muss ich zeigen, dass
1. [mm] $g\in\mathcal{O(f)}$ [/mm] liegt.
2. die Vereinigung vieler $g(n)$ die in [mm] $\mathcal{O}(f)$ [/mm] liegen auch weiterhin in [mm] $\mathcal{O}(f)$ [/mm] liegt.
3. (habe ich etwas vergessen ?)
Überlegung zu:
1. Ich wähle [mm] $n_0 [/mm] = 1$ und $c = 1$. Eingesetzt ergibt das nach der Erinnerung aus der Aufgabendefinition: $g(n) = 1 [mm] \cdot [/mm] f(n)$.
Die Laufzeit aller g liegt also in [mm] $\mathcal{O}(f)$.
[/mm]
2. Hier weiß ich nicht so genau weiter, kann ich so etwas annehmen wie: Seien $a(n), b(n) [mm] \in \mathcal{O}(f)$, [/mm] so gilt auch für diese:
$a(n) [mm] \leq c_a \cdot [/mm] f(n)$ für alle $n [mm] \geq n_a$ [/mm] (selbes für $b$). Es gilt also auch: $a(n) + b(n) [mm] \leq c_a \cdot [/mm] f(n) + [mm] c_b \cdot [/mm] f(n) = f(n) [mm] \cdot (c_a [/mm] + [mm] c_b) \leq c_x \cdot [/mm] f(n)$ für [mm] $c_x \geq c_a [/mm] + [mm] c_b$.
[/mm]
Aus 1. und 2. folgt dann doch: [mm] $\mathcal{O}(f) [/mm] = [mm] \mathcal{O}(g)$, [/mm] richtig?
Danke für eure Hilfe! :)
Liebe Grüße,
Chris
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:45 Di 21.04.2015 | | Autor: | fred97 |
> Beweisen Sie, dass [mm]\mathcal{O}(f) = \bigcup_{g\in\mathcal{O}(f)}^{}\mathcal{O}(g)[/mm].
>
> Zur Erinnerung: Für zwei Funktionen [mm]f,g : \mathbb{N} \rightarrow \mathbb{N}[/mm]
> schreiben wir [mm]f\in\mathcal{O}(g)[/mm], falls
> [mm]\exists c > 0, \exists n_0 > 0\forall n \geq n_0 : f(n) \leq c \cdot g(n)[/mm].
>
> Folgendes glaube ich verstanden zu haben:
> Damit die Aussage der Aufgabe stimmt muss ich zeigen,
> dass
>
> 1. [mm]g\in\mathcal{O(f)}[/mm] liegt.
> 2. die Vereinigung vieler [mm]g(n)[/mm] die in [mm]\mathcal{O}(f)[/mm]
> liegen auch weiterhin in [mm]\mathcal{O}(f)[/mm] liegt.
> 3. (habe ich etwas vergessen ?)
>
> Überlegung zu:
> 1. Ich wähle [mm]n_0 = 1[/mm] und [mm]c = 1[/mm]. Eingesetzt ergibt das
> nach der Erinnerung aus der Aufgabendefinition: [mm]g(n) = 1 \cdot f(n)[/mm].
>
> Die Laufzeit aller g liegt also in [mm]\mathcal{O}(f)[/mm].
>
> 2. Hier weiß ich nicht so genau weiter, kann ich so etwas
> annehmen wie: Seien [mm]a(n), b(n) \in \mathcal{O}(f)[/mm], so gilt
> auch für diese:
> [mm]a(n) \leq c_a \cdot f(n)[/mm] für alle [mm]n \geq n_a[/mm] (selbes für
> [mm]b[/mm]). Es gilt also auch: [mm]a(n) + b(n) \leq c_a \cdot f(n) + c_b \cdot f(n) = f(n) \cdot (c_a + c_b) \leq c_x \cdot f(n)[/mm]
> für [mm]c_x \geq c_a + c_b[/mm].
>
> Aus 1. und 2. folgt dann doch: [mm]\mathcal{O}(f) = \mathcal{O}(g)[/mm],
> richtig?
>
> Danke für eure Hilfe! :)
>
> Liebe Grüße,
> Chris
Nicht böse sein, aber obiges ist Murks.
1. Zeige $ [mm] \mathcal{O}(f)\subseteq \bigcup_{g\in\mathcal{O}(f)}^{}\mathcal{O}(g) [/mm] $
Dazu zeige: ist [mm] h\in \mathcal{O}(f), [/mm] so ex. ein [mm] g\in \mathcal{O}(f) [/mm] mit: [mm] h\in \mathcal{O}(g)
[/mm]
2. Zeige $ [mm] \mathcal{O}(f)\supseteq \bigcup_{g\in\mathcal{O}(f)}^{}\mathcal{O}(g) [/mm] $
Dazu zeige: ist [mm] g\in \mathcal{O}(f) [/mm] und [mm] h\in \mathcal{O}(g), [/mm] so ist [mm] h\in \mathcal{O}(f)
[/mm]
Beachte noch, dass stets [mm] f\in \mathcal{O}(f) [/mm] gilt.
FRED
|
|
|
|
