PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Phi, Omage, und O Notation


Supa
2006-10-07, 19:40:19
Brauche hilfe:

wie drücke ich die Phi Notation alleine durch die O Notation aus?

Trap
2006-10-07, 20:11:04
Phi? Meinst du Theta?

theta(x) = Schnittmenge von omega(x) und O(x)

Arokh
2006-10-07, 21:32:50
Vielleicht könntest du ein paar Worte darüber verlieren, was Phi und O Notation eigentlich für Tiere sind. Das würde zwar dir keinen Nutzen bringen, aber es könnte anderen Forennutzern dabei helfen zu verstehen, um was es überhaupt geht.

Supa
2006-10-07, 22:02:06
ja sorry, meinte theta...

Deffinition:
O(f(n))=c,no>0, n >= n0, f(n)<=c*g(n) (obere grenze einer funktion)
Omega(f(n))=c,no>0, n >= n0, f(n)>=c*g(n) (unteregrenze einer funktion)

Theta(f(n))=c1,c2,no>0, n >= n0, c1*g(n)<=f(n)<=c2*g(n) (beides zusammen)

Arokh
2006-10-08, 07:45:23
ja sorry, meinte theta...

Deffinition:
O(f(n))=c,no>0, n >= n0, f(n)<=c*g(n) (obere grenze einer funktion)
Omega(f(n))=c,no>0, n >= n0, f(n)>=c*g(n) (unteregrenze einer funktion)

Theta(f(n))=c1,c2,no>0, n >= n0, c1*g(n)<=f(n)<=c2*g(n) (beides zusammen)
1) wäre es möglich, daß du diese drei Definitionen in einer etwas allgemeinverständlicheren Sprache formulierst? Die erste Zeile z.B. ist nur eine Auflistung von 1 Gleichung und 3 Ungleichungen, wo soll da eine Definition drin enthalten sein? Meine Vermutung ist, daß da so etwas stehen sollte wie "für alle no > 0 gibt es ein n..."

2) daß das Funktionsargument n heißt, steht das dafür, daß nur natürliche Zahlen als Argument zulässig sind? Dann handelt es sich aber nicht um eine Funktion, sondern um eine Folge.

3) bedeuten obere und untere Grenze Maximum und Minimum?

4) ist no dasselble wie n0?

5) was ist g(n)?

6) offenbar handelt es sich um reine Mathematik, ohne jeglichen Bezug zur Programmierung, warum schreibst du so etwas im Programmierforum? Für solche Zwecke gibt es das OffTopic-Forum.

7) Die Schreibweise O(f(x)) wird auch benutzt, um die Ordnung einer Funktion anzugeben, gibt zu deinem O(f(n)) einen Zusammenhang?

Gast
2006-10-08, 09:45:32
[...]
6) offenbar handelt es sich um reine Mathematik, ohne jeglichen Bezug zur Programmierung, warum schreibst du so etwas im Programmierforum? Für solche Zwecke gibt es das OffTopic-Forum.
[...]

Die O Notation ist eine in der Informatik übliche Bewertungsweise für das asymptotische Laufzeitverhalten eines Algorithmus, also durchaus in diesem Forum angebracht.
Was obige, tatsächlich nicht vollständige Gleichungen heißen sollen, ist prosaisch relativ schnell erklärt:

O gibt die obere Schranke an, langsamer läuft der Algorithmus nie.
Omega steht für die untere Schranke, schneller gehts nicht.
Und Theta ist die "genaue" Schranke.

Alle diese Definitionen unter dem Vorbehalt, daß 2 Algorithmen mit dem selben asymptotischen Laufzeitverhalten sehr wohl auch unterschiedliche Laufzeit haben können, diese Notation steht am ehesten dafür, wie gut der Algorithmus für steigende Inputgrößen skaliert.

Und zu den mathematischen Definitionen:

g(n) = O(f(n)) bedeutet: es gibt ein n0 (Größe des Inputs, bei Sortieralgorithmen z.B. Größe des zu sortierenden Arrays) und eine natürliche Zahl c > 0, sodaß gilt: g(n) < c*f(n) für n > n0.

Grafisch hieße das, wenn ich die Laufzeit von g in Abhängigkeit von n auftrage, und dasselbe mit f mache, kann ich f durch Multiplikation mit einer Konstanten so nach oben verschieben, daß ab einem bestimmten n der Graph von f _immer über_ dem Graphen von g liegt.

Spiegelgleich für Omega, ab einem gewissen n gibt es ein c, für das f _immer unter_ g liegt.

Und Theta? Es gibt 2 c's, und der Graph von g liegt ab einem bestimmten n immer dazwischen.

Was heißt das jetzt? Interessant ist das "ab einem bestimmten n". Es kann durchaus sein, daß dieses n einen Wert hat, der bei normalem Einsatz des Algorithmus nie erreicht wird, darum auch "asymptotisch".
Und es kann auch sein, daß 2 Algorithmen mit dem selben asymptotischen Verhalten tatsächlich immer unterschiedlich schnell sind.

Beispiele:
O(1) wäre konstante Laufzeit. Wurscht, wie groß der Input ist, ich brauch immer gleich lang. Z.B.: Feststellen, ob Zahl gerade oder ungerade ist. Schau das letzte Bit an, egal, wie groß die Zahl ist.
Asymptotisch gesehen hätten also 2 Algorithmen, von denen der eine für jeden Input 1 Sekunde, der andere 1 Stunde braucht, dieselbe Laufzeit. In der Praxis wird man wohl ersteren vorziehen.

O(n) ist linear. Verdoppelt sich der Input, verdoppelt sich die Laufzeit. Z.B: alle Elemente eines Arrays ausgeben. Da muß ich halt alle durchlaufen.
Asymptotisch haben jetzt 2 Algorithmen auch dann dieselbe lineare Laufzeit, wenn der eine n+27 und der andere n+1.234.567 braucht. Weil sich ab einem bestimmten n die Konstante nicht mehr auswirkt. Bis dorthin ist allerdings auch hier ersterer klar zu bevorzugen :-)

O(n^2) ist quadratische Laufzeit.

O(2^n) exponentiell.

u.s.w.

Und was bringt das jetzt alles? Nun, ich weiß aus der Theorie, daß ich nie schneller als O(n*log n) sortieren kann. Hab ich jetzt einen Sortieralgorithmus geschrieben schau ich mir sein Laufzeitverhalten an. Seh ich, das Teil läuft mit O(n^12) sollte ich zurück ans Reißbrett.

Hab ich einen Algorithmus mit O(2^n) seh ich, das Teil skaliert absolut nicht gut. Das kann mir jetzt bei meiner konkreten Anwendung egal sein, wenn ich weiß, daß n immer nur geringe Werte annimmt, aber ich kann die grundsätzliche Qualität des Algorithmus bewerten.

So, soweit zur Theorie. Was war jetzt eigentlich nochmal die Frage? :-)
Aja, Theta durch O Notation ausdrücken.
Wenn man die mathematischen Definitionen vor sich hat ist das reine Abschreibübung:
f(n) = O(g(n)) und g(n) = O(f(n)).

Mittlerweile klar, wieso?
Und ich bitte, etwaige mathematisch unkorrekte Ausdrücke in obigem Elaborat zu verzeihen, ich bin Anwender, kein Theoretiker ;-)

mfg
mdk

Gast
2006-10-08, 09:47:13
Hoppla, da fehlte ein Häkchen :-)
Jeder Daumen nach unten war ein (n), also heißt die Schlußerkenntnis:

f(n) = O(g(n)) und g(n) = O(f(n)).

Beim Rest möge man sich das im Kopf editieren...

mfg
mdk

Gast
2006-10-08, 09:47:13
Hoppla, da fehlte ein Häkchen :-)
Jeder Daumen nach unten war ein (n), also heißt die Schlußerkenntnis:

f(n) = O(g(n)) und g(n) = O(f(n)).

Beim Rest möge man sich das im Kopf editieren...

mfg
mdk

Gnafoo
2006-10-08, 13:57:33
http://www.linux-related.de/coding/o-notation.htm

vielleicht hilft dir das ein wenig fürs Verständnis der Mengenschreibweise. Ist zwar nur O-Notation und nicht Omega und Theta, aber die funktionieren im Prinzip ganz genauso.

1) wäre es möglich, daß du diese drei Definitionen in einer etwas allgemeinverständlicheren Sprache formulierst? Die erste Zeile z.B. ist nur eine Auflistung von 1 Gleichung und 3 Ungleichungen, wo soll da eine Definition drin enthalten sein? Meine Vermutung ist, daß da so etwas stehen sollte wie "für alle no > 0 gibt es ein n..."
Nur um das für zukünftige Diskussionen zu klären. Die Definitionen (wie ich sie kenne) lauten:

http://www.forkosh.com/mimetex.cgi?O(f( n)):=\{g( n) | \exists c>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le g( n) \le c \cdot f( n) \} \\ \Omega(f( n)):=\{g( n) | \exists c>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le c \cdot f( n) \le g( n) \} \\ \Theta(f( n)):=\{g( n) | \exists c_1>0 \exists c_2>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le c_1 \cdot f( n) \le g( n) \le c_2 \cdot f( n) \}

tokugawa
2006-10-08, 16:10:03
6) offenbar handelt es sich um reine Mathematik, ohne jeglichen Bezug zur Programmierung, warum schreibst du so etwas im Programmierforum? Für solche Zwecke gibt es das OffTopic-Forum.


Informatik ist wie die Mathematik eine Formalwissenschaft. Diese Definitionen sind zwar mathematisch, entspringen allerdings aus einer Disziplin der Informatik (bzw. dem Schnittpunkt zwischen Mathematik und Informatik), nämlich der Komplexitätstheorie.

Das hat mit Programmierung zu tun wie nur sonst irgendwas, denn es geht darum, wie "schnell" Algorithmen sind bzw. wie gut sie skalieren nach verschiedenen Instanzgrößen.

Gast
2006-10-08, 17:37:29
2) daß das Funktionsargument n heißt, steht das dafür, daß nur natürliche Zahlen als Argument zulässig sind? Dann handelt es sich aber nicht um eine Funktion, sondern um eine Folge.Eine Folge ist eine Funktion, nämlich eine spezielle (von den natürlichen Zahlen auf irgendwas).
http://www.linux-related.de/coding/o-notation.htm

vielleicht hilft dir das ein wenig fürs Verständnis der Mengenschreibweise. Ist zwar nur O-Notation und nicht Omega und Theta, aber die funktionieren im Prinzip ganz genauso.


Nur um das für zukünftige Diskussionen zu klären. Die Definitionen (wie ich sie kenne) lauten:

http://www.forkosh.com/mimetex.cgi?O(f( n)):=\{g( n) | \exists c>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le g( n) \le c \cdot f( n) \} \\ \Omega(f( n)):=\{g( n) | \exists c>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le c \cdot f( n) \le g( n) \} \\ \Theta(f( n)):=\{g( n) | \exists c_1>0 \exists c_2>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le c_1 \cdot f( n) \le g( n) \le c_2 \cdot f( n) \}Muss g(n) umbedingt > 0 sein? Da kann man sicher drüber streiten, weil es ja keinen negativen Aufwand gibt. Für die rein mathematische Definition ergibt das schon Sinn, hat aber in der Informatik keinerlei Bedeutung.

Aber ansonsten hast du Recht, dass es Mengen von Funktionen sind. Sowas wie "O(n) =" (ist gleich) ist genau genommen falsch, wenn rechts vom Gleichheitszeichen nicht eine Menge steht.

Arokh
2006-10-09, 10:23:39
http://www.linux-related.de/coding/o-notation.htm

vielleicht hilft dir das ein wenig fürs Verständnis der Mengenschreibweise. Ist zwar nur O-Notation und nicht Omega und Theta, aber die funktionieren im Prinzip ganz genauso.


Nur um das für zukünftige Diskussionen zu klären. Die Definitionen (wie ich sie kenne) lauten:

http://www.forkosh.com/mimetex.cgi?O(f( n)):=\{g( n) | \exists c>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le g( n) \le c \cdot f( n) \} \\ \Omega(f( n)):=\{g( n) | \exists c>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le c \cdot f( n) \le g( n) \} \\ \Theta(f( n)):=\{g( n) | \exists c_1>0 \exists c_2>0 \exists n_0 \in \mathbb{N} \forall n \ge n_0: 0 \le c_1 \cdot f( n) \le g( n) \le c_2 \cdot f( n) \}DAS is doch schon viel aussagekräftiger :)