Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))? |
01.05.2010, 13:17 | crt | Auf diesen Beitrag antworten » | ||
Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))? wir sollen (in Informatik, kann also sein, dass die das mit der Mathematik nicht so ganz genau nehmen ) folgende Rechenregel zeigen: Dabei seien jeweils die Produkte der einzelnen Elemente. Mein Löungsansatz war folgender: Das Problem ist jetzt aber bei "", dass nur weil existiert, die einzelnen limsup nicht existieren müssen. Ist daher die Rückrichtung im Allgemeinen falsch? Ich bräuchte dann dazu ein Gegenbeispiel, ich hab mir bisher folgendes konstruiert: Hab ich irgendwas komplett falsch gemacht, oder stimmt das so? Grüße |
||||
01.05.2010, 16:51 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))?
Hallo! Du hast natürlich: und Also auch: Meintest du diese Richtung? Grüße Abakus |
||||
01.05.2010, 17:33 | crt | Auf diesen Beitrag antworten » | ||
Ich meinte analog zum Beweis bastel ich mir folgendes: Der letzte limsup existiert ja nicht. Die einzelnen Aussagen (existenz der limsup) sind ja dann nach Definition äquivalent zu Naja, du hast ja gerade mein Gegenbeispiel widerlegt Das heißt ja dann, dass ob die Rückrichtung klappt, davon abhängt wie man die Produkte und Quotienten wählt. Reicht es wenn ich im Beweis eine passende (sodass die "neuen" limsup jeweils existieren) Zerlegung fordere? |
||||
01.05.2010, 19:46 | Abakus | Auf diesen Beitrag antworten » | ||
Du musst schon zeigen, dass so eine Zerlegung existiert oder es widerlegen. Die Schreibweise der Behauptung soll wirklich bedeuten, dass du die Gleichheit der beiden Mengen zeigen sollst? (ich bin auch gerade am überlegen..) Grüße Abakus |
||||
02.05.2010, 11:02 | crt | Auf diesen Beitrag antworten » | ||
Ok, hab jetzt nochmal nachgefragt und analog zu schreibt man wohl Wäre aber trotzdem interessant, falls jemand ein Gegenbeispiel oder einen vollständigen Beweis findet. |
||||
06.05.2010, 00:03 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))?
bedeutet ja vermutlich (f, g nicht Null): und Jetzt noch miteinander multiplizieren und richtig schließen. Grüße Abakus |
||||
Anzeige | ||||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|