Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | O-Notation die Dritte

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge

eulerscheZahl

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.

Shizmo

O-Notation die Dritte

Hallo Wink

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