O-Notation Additionsregel (Beweis) |
14.02.2012, 18:03 | Auf diesen Beitrag antworten » | ||
rawfood | O-Notation Additionsregel (Beweis) 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. Allerdings habe ich vom Beweisen nicht wirklich Ahnung bitte daher um Hilfe. Danke |
||
|
|||
15.02.2012, 12:31 | Auf diesen Beitrag antworten » | ||
Karlito | Hallo, wie ist bei euch Ich kenne folgende Definition, welche das den Beweis rel. einfach macht: 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, 17:54 | Auf diesen Beitrag antworten » | ||
rawfood | 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, 19:15 | Auf diesen Beitrag antworten » | ||
rawfood | Heißt |
||
Anzeige | |||
|
|||
15.02.2012, 20:11 | Auf diesen Beitrag antworten » | ||
Karlito | Nein, nicht ganz. Du musst also nachweisen, dass es ein 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, 23:45 | Auf diesen Beitrag antworten » | ||
rawfood | Danke Karlito. Heißt das jetzt für den Fall, dass 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 |
||
16.02.2012, 12:26 | Auf diesen Beitrag antworten » | ||
Karlito | Wieso soll denn auf der Linken Seite das g(n) einfach wegfallen? Da du weist, dass Ein kleines Problem ist noch das VG, Karlito |
||
16.02.2012, 19:38 | Auf diesen Beitrag antworten » | ||
rawfood | Zu deiner Frage: Ich nahm eigentlich an, dass ich folgendermaßen in die Definition einsetzen muss : Wie siehts denn nun für den zweiten Fall aus? Ich werde mich später der Multiplikation widmen. Bin mal gespannt ob ich da mit deinen Tipps jetzt weiterkomme. |
||
16.02.2012, 22:55 | Auf diesen Beitrag antworten » | ||
Karlito |
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. Hier liegt jedoch der Fehler... Es muss heißen: Kann sein, dass das nur aus versehen war... Aber was du geschrieben hast ist halt trotzdem falsch... VG, Karlito |
|