Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))?

Neue Frage »

crt Auf diesen Beitrag antworten »
Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))?
Hallo,
wir sollen (in Informatik, kann also sein, dass die das mit der Mathematik nicht so ganz genau nehmen Augenzwinkern ) 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
Abakus Auf diesen Beitrag antworten »
RE: Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))?
Zitat:
Original von crt
Ich bräuchte dann dazu ein Gegenbeispiel, ich hab mir bisher folgendes konstruiert:



Hab ich irgendwas komplett falsch gemacht, oder stimmt das so?


Hallo!

Du hast natürlich:

und

Also auch:



Meintest du diese Richtung?

Grüße Abakus smile
 
 
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 smile

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?
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von crt
Reicht es wenn ich im Beweis eine passende (sodass die "neuen" limsup jeweils existieren) Zerlegung fordere?


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 smile
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.
Abakus Auf diesen Beitrag antworten »
RE: Landau-Symbole, Rechenregel O(f(n))*O(g(n))=O(f(n)*g(n))?
Zitat:
Original von crt


bedeutet ja vermutlich (f, g nicht Null):

und

Jetzt noch miteinander multiplizieren und richtig schließen.

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »