O-Notationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es soll die Gültigkeit (ausgehend von den entsprechenden Definitionen) folgender Aussagen gezeigt werden:
1.)
[mm] f(n)=O(g(n)\wedge f(n)=\Omega(g(n))=>f(n)=\Theta(g(n))
[/mm]
2.)
[mm] f(n)=O(a(n)\wedge [/mm] g(n)=O(b(n))=>f(n)+g(n)=O(max(a(n),b(n))
3.)
[mm] f(n)=O(a(n)\wedge [/mm] g(n)=O(b(n))=>f(n)*g(n)=O(a(n)*b(n)) |
Hallo Leute,
ich habe ein großes Problem bei der Aufgabe beim Punkt "Zeigen".
Hat zufällig jemand eine Idee wie man vorgehen könnte?
Vielen Dank im Voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:16 Mi 27.11.2013 | | Autor: | wieschoo |
Beachte, dass man [mm]f(n)\in \mathcal{O}(g(n))[/mm] schreiben muss. Die Funktion ist ein Element von der Menge [mm] $\mathcal{O}(g(n))$!
[/mm]
So wie es da steht ist es falsch.
Was habt ihr als Definitionen von den Landau-Notationen?
|
|
|
| |
|
Seien $f,g$ Funktionen mit [mm] $f\in\mathcal{O}(g)$ [/mm] und [mm] $f\in [/mm] o(g)$, d.h.
(Definition von [mm] $\mathcal{O}$ [/mm] einfügen) und (Definition von $o$ einfügen). Wir zeigen [mm] $f\in\Theta(g), [/mm] d.h. $(Definition von [mm] $\Theta$ [/mm] einfügen).
Dann steht es eigentlich da.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:42 Do 28.11.2013 | | Autor: | mtr-studi |
Ich habe es jetzt soweit hinbekommen, aber ich bin mir in einigen Sachen noch nicht ganz schlüssig. Insbesondere bei dem zweiten und dritten Fall.
Heute habe ich keine Zeit mehr, aber ich reiche die Definitionen morgen nach und vielleicht kannst du mir dann ja bei den Beweisen etwas helfen.
|
|
|
| |
|
Ich habe es glatt mal wieder vergessen.
Also wir haben folgendes definiert
[mm] $f(n)=O(g(n)):<=>\exists c,n_o \forall~ [/mm] n [mm] \ge n_0:f(n) \le [/mm] c*g(n)$
[mm] $\Omega(g)=\{f~|~\exists~c,n_0:\forall~n \ge n_0:~f(n)\ge c*g(n)\}$
[/mm]
[mm] $\Theta(g)=\{f~|~\exists c_1,c_2,n_0:\forall~n \ge n_0:c_1*g(n) \le f(n) \le c_2*g(n) \}$
[/mm]
Also bei der Nummer 1.) ergibt es sich ja einfach durch umstellen schon, aber bei 2.) und 3.) habe ich große Probleme.
Hättest du eine Idee wie ich dort vorgehen könnte?
Vielen Dank im Voraus!
|
|
|
| |
|
Du hast
[mm]f(n)\in\mathcal{O}(a(n))[/mm], d.h.
[mm]\exists c_f,n_0 \forall n\ge n_0 : f(n)\le c_f a(n)[/mm]
[mm]g(n)\in\mathcal{O}(b(n))[/mm], d.h.
[mm]\exists c_g,n_1 \forall n\ge n_1 : g(n)\le c_g b(n)[/mm]
und du sollst zeigen, dass
[mm]h(n):=f(n)+g(n)\in \mathcal{O}(\max\{a(n),b(n)\})[/mm], d.h.
[mm]\exists c_h,n_2 \forall n\ge n_2 : h(n)\le \max\{c_ha(n),c_hb(n)\}[/mm]
Jetzt schätze doch einmal $f(n)+g(n)$ nach oben ab mit den Sachen, die du hast.
|
|
|
|
