Transitivitaet der Landau-Notation.

Michael G. (linuxgeek) OP 26.10.2008 02:19 #1027803

Lesenswert?

•

Hallo Forum,

hier mal eine mathematische Problemstellung. Wahrscheinlich kennt Ihr ja 
die Landau-Notation:

$f \in \mathcal{O}(g)$


wobei man hier mit der asymptotischen oberen Schranke arbeit, so dass 
fuer obige Aussage gelten muss:

$0 \le \limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty$


Das heisst f ist in der Ordnung von g, falls der asymptotische Grenzwert 
definiert ist.

Die Operation ist transitiv, d.h.

$f(n) = \mathcal{O}(g(n)) \and g(n) = \mathcal{O}(h(n)) \Rightarrow f(n) = \mathcal{O}(h(n))$


Wie koennte man dies am besten beweisen? Kommt man da mit den 
Rechenregeln des Limes hin mit oder sollte man einen konstruktiveren 
Ansatz waehlen?

Ich bitte um konstruktive Vorschlaege... ;)

Gruss,
Michael

Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden

Jörg Gast 26.10.2008 08:55 #1027827

Lesenswert?

•

▲
▼

Vergiss die math. Äquivalenz zum "0 <= lim sup |..|<.." und betrachte
die Definition des Landau-Symbols O(f): es ex. ein C,Epsilon so dass..
(z.B. auf Wikipedia). Du erhältst zur linken Seite deiner Behauptung
ein C1,Eps1 für f=O(g) und ein C2,Eps2  für g=O(h). Damit bastelst du
dir einfach ein C3,Eps3 so dass f=O(h).

Gruss

Jörg

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Katapulski Gast 26.10.2008 09:03 #1027832

Lesenswert?

•

▲
▼

Alle Achtung! Was es nicht alles gibt...

IKSLUPATAK ist die umgekehrte Notation  von Katapulski.

gez. Katapulski

Antwort Zitieren Bearbeiten Löschen Beitrag melden

klodeckel Gast 26.10.2008 21:13 #1028417

Lesenswert?

•

▲
▼

ja, ich bin auch zutiefst beeindruckt.

guude

ts

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Menschenkenner Gast 27.10.2008 09:22 #1028657

Lesenswert?

•

▲
▼

Mein Gott, ist das löten einer Platine so banal...ich schäme mich für 
mein Präkariaten dasein.

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Bernd G. Gast 27.10.2008 10:34 #1028716

Lesenswert?

•

▲
▼

Was ist eigentlich aus den transitiven Hüllen geworden?
Beitrag "praktische Informatik (transitive Hülle)"

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Jango Gast 27.10.2008 11:56 #1028804

Lesenswert?

•

▲
▼

> ja, ich bin auch zutiefst beeindruckt.

Ich nicht. Ist doch nur Informatik Grundstudium :-)

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren