Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation die Dritte

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

O-Notation die Dritte

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

O-Notation die Dritte

Zitatantwort auf diesen Beitrag erstellen

Hallo

Zitat:

Gegeben sind zwei Funktionen $[latex]f_1,f_2: \mathbb{N} \to \mathbb{R^{+}}[/latex]$ , für die gilt $[latex]f_1 \in \mathcal{O}(g)[/latex]$ und $[latex]f_2 \in \mathcal{O}(g)[/latex]$ .
Beweisen oder widerlegen Sie folgende Aussagen:

$[latex]f_1 + f_2 \in \mathcal{O}(g)[/latex]$
$[latex]f_1 - f_2 \in \mathcal{O}(1)[/latex]$
$[latex]f_1 * f_2 \in \mathcal{O}(g^2)[/latex]$
$[latex]\frac{f_1}{f_2} \in \mathcal{O}(1)[/latex]$
$[latex]f_1 \in \mathcal{O}(f_2) \wedge f_2 \in \mathcal{O}(f_1)[/latex]$
$[latex]f_1 \in \mathcal{O}(f_2) \vee f_2 \in \mathcal{O}(f_1)[/latex]$

Ok, als erstes mal die Frage, was genau gemeint ist mit "beweisen", einfach nur zeigen oder wirklich mathematisch beweisen? Wie würde denn so ein Beweis denn ausschauen?

Also ich würde es so machen, weiß aber nicht ob man das so einfach machen darf:

$[latex]\mathcal{O}(g) + \mathcal{O}(g) = \mathcal{O}(g+g) = \mathcal{O}(g)[/latex]$ also richtig.
$[latex]\mathcal{O}(g) - \mathcal{O}(g) = \mathcal{O}(g-g) = \mathcal{O}(g)[/latex]$ also falsch.
$[latex]\mathcal{O}(g) * \mathcal{O}(g) = \mathcal{O}(g*g) = \mathcal{O}(g^2)[/latex]$ also richtig.
$[latex]\frac{\mathcal{O}(g)}{\mathcal{O}(g)} = \mathcal{O}(\frac{g}{g}) = \mathcal{O}(1)[/latex]$ also richtig.

Bei 5 und 6 kenn ich mich nicht ganz aus...

LG

15.03.2016 21:02

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

2. Begründung gefällt mir nicht.
Nimm z.B. f1 = 2*g und f2=g.
Mit solchen Beispielen würde ich auch die Korrektheit von Aussage 5 zeigen. Aussage 6 ist dann sowieso wahr, wenn 5 es ist.

__________________
Syntax Highlighting fürs Board (Link)

17.03.2016 09:31

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation die Dritte