Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Sortieren nach Inklusion

Sortieren nach Inklusion

Universität / Fachhochschule

Funktionalanalysis

Inklusion-Exklusion

Tags: Funktionalanalysis, Inklusion-Exklusion, O-Notation

dani87 aktiv_icon

16:30 Uhr, 11.10.2016

Hallo!
Ich soll Funktionsklassen nach Inklusion sortieren und idtentische Klassen kennzeichen bzw. deren Identität beweisen.

Ich habe nun folgende Lösung gefunden:
O(7)<O(ln n)=O(log8 n)<O(4n)<O(n^(ln 7))<O(n^3)=O(8^()log2 n)<O(3^n)<O(5^n)<O(n!)<O(n^n)

Zum Beweis der beiden Identitäten:
O(n^3)=O(8^(log2 n))=O(n^(log2 8)) Aus (log2 8)=log(8)/log(2)=3, somit O(n^3) korrekt

O(log8 n))=log(n)/log(8) =>log(8)ist ein Konstanter Faktor und kann vernachlässig werden, daher log(n)

Sind meine Annahme soweit richtig, bitte um Rückmeldung!

MFG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

ermanus aktiv_icon

17:15 Uhr, 11.10.2016

Hallo dani87,
ich habe Probleme mit Deiner Schreibweise.
Meinst Du mit "

O (f) < O (g)

" die echte Inklusion

{h ∣ h = O (f)} \subset {h ∣ h = O (g)}

,
wobei mit

O

das Landau-Symbol gemeint ist ?

Wenn ich das so richtig interpretiert habe, ist Deine
Inklusionskette mit den 2 Gleichungen meines Erachtens nach
korrekt. Du hast aus Versehen einmal

O (3^{n})

zu viel drin.

Gruß ermanus

dani87 aktiv_icon

18:54 Uhr, 11.10.2016

Hallo!
Sorry, ja ich meine die echte Inklusion!
Das O steht für die O-Notation, in meinem Fall für die Analyse der Laufzeit von Algorithmen.
Danke und LG

dani87 aktiv_icon

11:13 Uhr, 15.10.2016

Hallo!
Ich habe nochmals ein Bsp zu lösen bekommen. Ich bitte darum mir kurz zu sagen, ob meine Lösung korrekt ist:

Folgende Funktionsklassen habe ich nach Inklusion sortiert:

O (8) \subset O (l n (n^{8})) = O (l o g_{8} n) \subset O (8 n) \subset O (n^{l n 8}) \subset O (n^{3}) = O (8^{l o g_{2} (n)}) \subset O (3^{n}) \subset O (8^{n}) \subset O (n!)

Identische Klassen:

O (l n (n^{8}) = 8 l n (n) = O (l n (n))

8 ist ein konstanter Faktor und kann vernachlässigt werden

O (l o g_{8} n) = \frac{l n (n)}{l n (8)} = O (l n (n))

ln(n) ist ebenfalls ein konstanter Faktor, somit sind diese beiden in der selben Klasse

O (n^{3}) = O (8^{l o g_{2} (n)}) = O (n^{l o g_{2} (8)}) = O (n^{\frac{l o g (8)}{l o g (2)}}) = O (n^{3})

Somit ebenfalls in der gleichen Klasse

Bin mir vor allem bei den Klassenzugehörigkeiten nicht ganz sicher!

Vielen Dank!

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1327963

1327156

	Status: nicht eingeloggt	Noch nicht registriert?