Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation Additionsregel (Beweis)

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

O-Notation Additionsregel (Beweis)

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

rawfood
Grünschnabel

Dabei seit: 14.02.2012
Beiträge: 7

O-Notation Additionsregel (Beweis)

Zitatantwort auf diesen Beitrag erstellen

Hey Leute,

Ich hab ein Problem damit. Wie beweist man sowas?

Seien T1(n) und T2(n) die Laufzeiten zweier Programmstücke P1
und P2. Sei ferner T1(n) = O(f(n)) und T2(n) = O(g(n)). Beweisen Sie folgende Eigen-
schaften der O-Notation:
• Additionsregel: T1(n) + T2(n) = O(max (f(n), g(n)))
• Multiplikationsregel: T1(n) · T2(n) = O(f(n) · g(n))

Bei der Additionsregel ist klar: T1(n)+T2(n)=O(f(n))+O(g(n))=O(f(n)+g(n))=
Je nach Fall entweder O(f(n)) oder O(g(n)) was schließlich zur anderen Schreibweise O(max(f(n), g(n))) führt.

Und bei der Multiplikation würde ich nur die Schritte zeigen. $[latex]T_{1}(n)\cdot T_{2}(n)=O(f(n)\cdot O(g(n))=O(f(n)\cdot g(n))[/latex]$

Allerdings habe ich vom Beweisen nicht wirklich Ahnung bitte daher um Hilfe.

Danke

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von rawfood: 14.02.2012 18:03.

14.02.2012 18:03

Nehmen Sie rawfood in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

wie ist bei euch $[latex] \mathcal{O}(g(n)) [/latex]$ definiert?

Ich kenne folgende Definition, welche das den Beweis rel. einfach macht:

$[latex] f(n) = \mathcal{O}(g(n)) \Leftrightarrow (\exists c > 0) (\exists n_0 \in \mathbb{N}) (\forall n \ge n_0) f(n) \le c \cdot g(n) [/latex]$

Vlt kommst du ja damit selbst auf die Beweise. Der Rest ist eigtl nur einsetzen und ein wenig Fallunterscheidung. Poste deine Lösung bitte oder frag einfach noch mal nach.

VG,

Karlito

15.02.2012 12:31

Nehmen Sie Karlito in Ihre Freundesliste auf

rawfood
Grünschnabel

Dabei seit: 14.02.2012
Beiträge: 7

Die Definition ist mit meiner identisch. Allerdings steht bei mir im Skript f statt f(n) und O(g) anstatt O(g(n). Also f=O(g):<weitere Definition>

O(g(n)) ist also f(n) mit der Bedingung, dass f(n) kleiner gleich als g(n) multipliziert mit der Konstante c.

O(f(n)) heißt dann im Umkehrschluß, dass g(n) kleiner gleich c*f(n) ist? Wäre dann O(f(n)) gleich g(n)?

Hieße O(g(n))+O(f(n)) nun f(n) + g(n)? Ich krieg das nicht auf die Kette. Mir wird nicht klar, wie ich die Definition für meinen Beweis ausnutze.

Hast du einen Tipp wie ich einen Schritt weiter komme?

vg
rf

15.02.2012 17:54

rawfood
Grünschnabel

Dabei seit: 14.02.2012
Beiträge: 7

Heißt $[latex]O(g(n))+O(f(n)) = f(n) \leq c \cdot g(n) + g(n) \leq c \cdot f(n))[/latex]$ ?

15.02.2012 19:15

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Nein, nicht ganz.

$[latex] f(n) = \mathcal{O}(max(f(n) +g(n))) \Leftrightarrow (\exists c > 0) (\exists n_0 \in \mathbb{N}) (\forall n \ge n_0) f(n)+g(n) \le c \cdot (max(f(n),g(n))) [/latex]$

Du musst also nachweisen, dass es ein [latex]c[/latex]

und ein

gibt, so dass

$[latex]f(n)+g(n) \le c \cdot (max(f(n),g(n))) [/latex]$

Damit hast du 2 Fälle zu betrachen. Zumindest wenn man vorraussetzt, dass f(n) immer kleiner oder größer als g(n) ist...

VG

15.02.2012 20:11

rawfood
Grünschnabel

Dabei seit: 14.02.2012
Beiträge: 7

Danke Karlito.

Heißt das jetzt für den Fall, dass $[latex]f(n) \leq g(n), dass f(n) \leq c \cdot g(n) [/latex]$
und umgekehrt, ist g(n) kleiner gleich c*f(n)?

Wäre jetzt konkret f(n)=n² und g(n) =n, dann wäre doch max(f(n),g(n))=f(n) was wiederum bedeuten würde, dass c=(n²+n)/n² wäre, und das würde gegen n konvergieren..... mhm.... Das ganze verwirrt mich. Wie drücke ich nun die Fallunterscheidung Mathematisch korrekt aus?

vg
rawfood

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von rawfood: 15.02.2012 23:45.

15.02.2012 23:45

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Wieso soll denn auf der Linken Seite das g(n) einfach wegfallen?

$[latex]<br /> f(n) + g(n) \le c \cdot g(n) & |:g(n) [/latex]$
$[latex]\frac{f(n)}{g(n)} +1 \le c [/latex]$

Da du weist, dass [latex]g(n) > f(n)[/latex]

, ist $[latex]\frac{f(n)}{g(n)} < 1[/latex]$ und somit brauchst du nur ein c wählen, welches größer als 2 ist und du hast nachgewiesen, dass es ein c gibt.

Ein kleines Problem ist noch das [latex]n_0[/latex]

. Ich denke man muss hier einfach vorraussetzen, dass es ein solches [latex]n_0[/latex]

gibt.

VG,

Karlito

16.02.2012 12:26

rawfood
Grünschnabel

Dabei seit: 14.02.2012
Beiträge: 7

Zu deiner Frage: Ich nahm eigentlich an, dass ich folgendermaßen in die Definition einsetzen muss :

$[latex]f(n)+g(n) \leq c \cdot g(n)+g(n)[/latex]$ Bei -g(n) würde sich dann g(n) egalisieren. Allerdings macht das ja wenig Sinn, weil die Rechte Seite nur die Schranke ausdrückt. Also mir war einfach nicht klar, wie ich nun die Definition nutzen muss. Sprich : $[latex]f(n)+g(n) \leq c \cdot g(n) [/latex]$ war mir als Ausdruck als solcher nicht klar. Dann war mir nicht klar, dass ich bei dem Nachweis zeigen muss, dass es ein c gibt. Ich hab bei c irgendwas mit einer Konstante im Sinn, die die schnelligkeit des Computersystems ausdrückt. Werde da wohl etwas durcheinander bringen.

Wie siehts denn nun für den zweiten Fall aus? $[latex]O(max(f(n),g(n)) : f(n) \geq g(n) [/latex]$
$[latex]f(n)+g(n) \leq c \cdot f(n) [/latex]$

$[latex]g(n)+1 \leq c [/latex]$

Ich werde mich später der Multiplikation widmen. Bin mal gespannt ob ich da mit deinen Tipps jetzt weiterkomme.

16.02.2012 19:38

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Zitat:

Original von rawfood

Wie siehts denn nun für den zweiten Fall aus? $[latex]O(max(f(n),g(n)) : f(n) \geq g(n) [/latex]$
$[latex]f(n)+g(n) \leq c \cdot f(n) [/latex]$

$[latex]g(n)+1 \leq c [/latex]$

Sry, aber das ist falsch. Der zweite fall ist analog dem ersten fall... max() gibt hier nur die andere Funktion zurück, wie du anfangs noch richtig eingesetzt hast.

$[latex]f(n)+g(n) \leq c \cdot f(n) [/latex]$

Hier liegt jedoch der Fehler...

$[latex]g(n)+1 \leq c [/latex]$

Es muss heißen:

$[latex]\frac{g(n)}{f(n)}+1 \leq c [/latex]$

Kann sein, dass das nur aus versehen war... Aber was du geschrieben hast ist halt trotzdem falsch...

VG,

Karlito

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 16.02.2012 22:56.

16.02.2012 22:55

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation Additionsregel (Beweis)