Wachstum von Funktionen

09.07.2004, 15:19	KalterKaffee	Auf diesen Beitrag antworten »
Wachstum von Funktionen Habe ein Problem mit dem Wachstum von Funktionen! Folgende Aufgabe: O(n^3) ist Teilmenge von O(n^2)? Ist das wahr oder falsch? Weiterhin weiß ich nicht was folgende Zeichen bedeuten: 1. ein Großes O mit einem Strich in der Mitte 2. ein Großes O das oben so geschweift ist 3. ein kleines o 4. so ein Ding dass auch aussieht wie ein großes O nur unten offen ist und nach aussen auf jeder Seite rausgeht. Vielen Dank im Voraus!
09.07.2004, 16:13	Shopgirl	Auf diesen Beitrag antworten »
Hallo KalterKaffee, kennst du die Definition der O-Notation? Diese wird als "gross-O-Notation" ausgesprochen, denn es gibt noch die "klein-o-Notation". Eine weitere Notation verwendet das "grosse O mit dem Strich in der Mitte": ein grosses Theta, $\begin{eqnarray} \theta \end{eqnarray}$ . Alle zusammen sind so genannte Landau-Symbole. In deiner Auflistung ist also 1. das Theta $\begin{eqnarray} \Theta \end{eqnarray}$ , unter 2. kann ich mir nichts vorstellen, sieht das so aus? $\begin{eqnarray} \tilde{O} \end{eqnarray}$ 3. ist das "Klein-o", und 4. ist ein grosses Omega, $\begin{eqnarray} \Omega \end{eqnarray}$ . Es gibt eine allgemeine Definition dieser Symbole. Da du die Variable n verwendest, gehe ich davon aus, dass du den Spezialfall fuer n gegen unendlich benutzt. (Es gibt noch den haeufig verwendeten Fall, dass die Variable gegen 0 geht, und prinzipiell jede andere reelle Zahl als Grenzwert, aber die werden kaum verwendet.) Dann schau dir nochmal deine Definition von O(n^3) und O(n^2) an, und schreib sie hierher, wenn du dir die Antwort dann noch nicht selbst geben kannst.
09.07.2004, 16:25	Mazze	Auf diesen Beitrag antworten »
Wir benutzen die Notation für Aufwandsabschätzungen von algorithmen $\begin{eqnarray} O(n) = n^2 \end{eqnarray}$ Aufwandsklasse, Abschätzung nach oben, Funktion wächst maximal so schnell $\begin{eqnarray} \Theta(n) \end{eqnarray}$ bedeutet die Funktion wächst identisch zur Abschätzung $\begin{eqnarray} \Theta(n) = n^2 \end{eqnarray}$ heißt also die Funktion wächst genau quadratisch $\begin{eqnarray} \Omega(n)=n^2 \end{eqnarray}$ ist abschätzung nach unten, die Funktion wächst also mindestens so schnell Ich weiß nicht ob es das ist was du brauchst, da wir das im Rahmen von Algorithmenabschätzung eingeführt haben.
11.07.2004, 15:52	KalterKaffee	Auf diesen Beitrag antworten »
Ja n geht gegen unendlich, kann mir aber net erklären wie dass ne Teilmenge sein soll, danke für jeden Tipp!
14.09.2004, 10:08	outlast	Auf diesen Beitrag antworten »
Ja die O-Notationen gliedern, wenn man so sagen will, die Funktionen nach ihrem Wachstum. z.B O(n) linear O(n^2) quadratisch O(n^3) kubisch usw. D.h dass z.B. die Funktion f(x)=3x + 2 Element von O(n) ist und z.B. f(x)=3x^3+4*x-2 Element O(n^3) ist. Kann mir jemand meine Überlegung bestätigen? Zudem habe ich eine interessante Aufgabe zu diesem Thema. Sei F={f: N->N} die Menge der Funktionen auf N. a) Zeigen Sie, dass durch R:={(f,g) element FxF \| f element O(g) und g element O(f)} eine Äquivalenzrelation auf F gegeben wird. b) Beweisen Sie dann, dass auf der MEnge F der Äquivalenzklassen von R durch [f]<=[g]; <=> [f] ist Teilmenge O(g) eine partielle Ordnung definiert wird. Aufgabe a konnte ich lösen. Denke ich mal! Aufgabe b bleibe ich leider hängen. kann mir da jemand weiter helfen?? Gruss & Danke oultlast
17.09.2004, 15:14	outlast	Auf diesen Beitrag antworten »
hmmm... weiss da niemand weiter?
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »