f1=o(f1), f1=O(f2), folgt daras, dass f = o(f2) ist?

1 Antwort

Nimm die Definition der Landau Notation, jenachdem welche Ihr benutzt hatte (die asymptotische oder die aussagenlogische).

klein o ist definiert wie folgt:

Für alle c > 0, gibt es ein n0 > 0 für das gilt f1 < c*f1 für alle n >= n0

Das kann schonmal nicht stimmen da f1=o (f1) (besser ist f1€o (f1) aber in der Informatik hat sich = eingegliedert obwohl es sich mathematisch um eine Menge von Funktionen handelt) offensichtlich nicht stimmt, da für c = 1 kein n0 geben kann.

4

Asymptotische haben wir, könnten Sie mir bitte das ganz ganz ausvöllig erklären, damit ich nach diesem Beispiel die andere Aufgaben lösen kann. Das Thema ist komplett neu für mich und es ist mir wirklich schwer es zu vertehen. 

0
13

Wie die asymptotische Definition lautet weiß Ich grad nicht, wir habens mit dieser hier gelernt. aber hier mal eine allgemeine Erklärung: Grundsätzlich gibt es 5 verschiedene solcher Klassen. O (f (x)) -> Das ist eine MENGE in der alle Funktionen drinne sind, die HÖCHSTENS so schnell sind wie f (x). Dabei werden Konstanten nicht berücksichtigt (daher das c) o (f (x)) -> Das ist die Menge in der alle Funktionen drinne sind die echt langsamer als f (x) sind. Omega -> Hier gilt, es sind alle Funktionen die MINDESTENS so schnell wie f (x) sind klein-Omega -> Hier sind alle Funktionen die echt schneller sind als f (x) und Theta -> Das sind alle Funktionen die so schnell sind wie f (x). Wenn man nun eine Aufgabe hat wie ist g (x)€ O (f (x)) dann musst du zeigen ob g (x) HÖCHSTENS so groß ist wie f (x) (das ist quasi in der definition drinne) indem du das umformst zu einer wahren Aussage oder einem Axiom.

1
4
@LashCash

Ok, danke für solche ausvöllige Erklärung. Es ist mir wirk2lich ein wenig klarer geworden, aber wie beweise ich den das mathematisch ? Muss man da irgendwelche beliebige Funktionen einsezten oder wie geht das? Es wäre Ihnen wirklich sehr dankbar, wenn Sie mir damit helfen könnten! 

0
13

Normalerweise hat man Funktionen gegeben für f (x) bzw. g (x). Bei deiner Aufgabe ist mir unklar ob das kleine o ein kleines o oder soch das Große O sein soll. Denn wenns das kleine o ist, macht es eben keinen sinn so

1
4
@LashCash

Die Aufgabe lautet genau so, wie es da steh, das sind 2 O-s? klein und groß

0
4
@Tanechka25

ich habe auch eine andere Aufgabe, vllt verstehen Sie es dann besser: f=O(f1), f1 = Ω(f2) ==>? f = O(f2)


oder die andere: f1 = Ø(g1), f2 = Ø(g2) -->? f1*f2 = Ø(g1*g2)




0

Was möchtest Du wissen?