Komplexitätsklassen

[Kuma]

Hey
Ich weiß zwar nicht ob das hier reinpasst, aber hier ist es noch am besten.
Habe da ein paar Fragen zu einem Übungsblatt, das ich zwar schon größtenteils beantwortet habe aber trotzdem sind ein paar Fragen geblieben.

So wie ich das verstehe ist O die Obergrenze, groß Omega die Untergrenze und Big Theta der average case eines Algorithmus?

Was heißt dann zB wiki die Funktion f€ O(g)?
So wie ich das verstehe doch nur, dass es eine Funktion f gibt welche langsamer steigt als die Funktion g ?
f € Omega (g) wäre für mich, dass f kleienr ist als g,aber hier steht in der Beschreibung sowie als Graph: "f ist in der Größenordnung Omega von g" und der Graph zeigt, dass f ab einem gewissen Zeitpunkt größer ist als g. Also kann bei meinem Verständnis etwas nicht stimmen...
Und bei Big Theta sind überhaupt 2 Graphen für g aufgezeichnet wobei f dazwischen liegt.
Des weiteren: es steht überall ein c dabei (bei der formalen Definition, zb Wiki) wofür ist diese Konstante?
Ich hab zb.: bei f@ O(g) dass f(n) <c *g(n) aber keine Ahnung warum da ein c dazukommt.

Nochn Bsp.: dazu:
Ich muss zeigen, welche Funktion zu f € O/Theta/Omega(g) gehört.

f = 198n^2 -12n +55 g=n^2
Das ist jetzt fast die gleiche wie von Wikipedia. Man sieht eigentlich, dass für kleine n f wesentlich kleienr ist als g, aber für große n nur noch n^2 relevant ist und somit ist hier f€O(g) gültig?
Oder
f= n^2 * n^(5/2) g= n^2 * (log(n)^17.5)^(1/2), hier würde ich wieder das gleiche behaupten.
Jedoch würde mich interessieren, wie eine Funktion für f€Theta(g) aussehen würde.

Wie kann ich überprüfen was für eine KOmplexität schneller ist?
Ich nehme mal einfach drei Beispiele. - aus dem Kontext gerissen sind die nicht so aussagekräftig aber es geht mir auch eher ums zeigen..

O(n*log(n) * log(log(n)))
O(n * log(n)^(1+E)) 0<E<1
O(n * ln(n))
O(n * log(n))

Mir ist klar, dass ich das einfach aufzeichnen kann, aber soweit ich weiß gibt es da noch einen weg das zu beweisen was auch eher verlangt ist, als einfach nur was hinzumalen.

Also, ich sage mal, dass O(n * log(n)) schneller steigt als O(n * ln(n)).
Mit der begründung, dass 2^x = 128 ein höheres x benötigt als e^x=128, also müsste bei der "Formel" immer ein höherer Wert rauskommen und schneller steigen.
Ich gehe mal davon aus, dass O(n*log(n) * log(log(n))), langsamer steigt als O(n * log(n)^(1+E)) , aber kann nicht zeigen weshalb genau.

 

[Harzerkas]

O(n * log(n))=O(n * ln (n)) da du beim Logarithmus die Basiswechseln kannst!

 

[nVentor]

Ui, ganz schön viel auf einmal. Ich fang mal mit einer Frage an, die nicht allzuschwer zu beantworten ist.

Wie kann ich überprüfen was für eine KOmplexität schneller ist?

Ich nehme mal an, du meinst, "welche Funktion schneller wächst"

Das geht im Prinzip ganz einfach, indem du den Grenzwert gegen Unendlich des Betrages von f(x)/g(x) betrachtes und schaust, ob es konvergiert oder über alle Grenzen wächst. Wenn es konvergiert, dann muss g(x) mindestens so schnell wachsen, wie f(x), wenn nicht, dann nicht.

Dann noch zu

hier steht in der Beschreibung sowie als Graph: "f ist in der Größenordnung Omega von g" und der Graph zeigt, dass f ab einem gewissen Zeitpunkt größer ist als g.

das passt doch. f € Omega(g) heißt doch, dass f für hinreichend große n größergleich g.

ebenso

[/Quote]Und bei Big Theta sind überhaupt 2 Graphen für g aufgezeichnet wobei f dazwischen liegt.[/Quote]

Genau so soll es auch sein. Theta steht für "liegt zwischen gewissen oberen und unteren Schranken." Wenn f zwischen zwei Kurven verläuft, dann sind diese doch obere und untere Schranke.

Was die Konstante c betrifft, bin ich von WP gerade selbst etwas verwirrt. Vielleicht komm ich noch drauf.


So, das war aber schonmal ein Anfang. Ich hoffe, es hilft.

 

[Sukrim]

Die Konstante C kommt aus der Definition:

Z.B. für O(n): Es existiert eine Konstante c und ein gewisser "Startwert" x(0) für die gilt: Ab dem "Startwert" x(0) sind alle Funktionswerte kleiner/gleich einer linearen Funktion mit Steigung c.

Das kann umgekehrt auch heißen, dass ein Algorithmus (je nach x(0) ) SEHR lange Zeit ganz anderes Verhalten zeigen kann - aber irgendwann wird er eben max. linear ansteigen. Die Steigung kann auch ziemlich heftig sein, aber linear ist linear - das sagt das c aus.

Bei Logarithmen solltest du nochmal in deinem Skript nachlesen, das ist ähnlich wie mit linearen Funktionen: f = 2x wächst auch langsamer als g= 4x, trotzdem fallen beide in die gleiche Klasse (lineare Steigung).

Da man es hier immer mit Grenzwerten zu tun hat, ist selbst eine in der Praxis nutzlose Aussage über Algorithmen, wo f = 10^999999999*x und g=x^2 aussagt, dass f=O(n) und g=O(n^2) ist (aber eben mit einem sehr hohen x(0)) trotzdem gerechtfertigt, da es eben einen Punkt gibt ab dem g immer größer als f ist, egal wie weit weg der ist, oder wie steil f anfangs ansteigt.

 

[Kuma]

O(n * log(n))=O(n * ln (n)) da du beim Logarithmus die Basiswechseln kannst!

Hmm vielleich verstehe ich deine Aussage nicht richtig...
Aber es wurde am Anfang definiert, dass log zur Basis 2 und ln zur Basis e ist.

Das geht im Prinzip ganz einfach, indem du den Grenzwert gegen Unendlich des Betrages von f(x)/g(x) betrachtes und schaust, ob es konvergiert oder über alle Grenzen wächst. Wenn es konvergiert, dann muss g(x) mindestens so schnell wachsen, wie f(x), wenn nicht, dann nicht.

Du sagst "mindestens" kann ich dann auf jeden Fall davon ausgehen, dass f dann größer ist oder kann ich Gleichheit ein Fall sein?
Hmm in Analysis haben wir nie was mit log gemacht, könntest du mal vielleicht nen Link dazu bzw Gesetz einwerfen?
Habe es mal so probiert, nach dem Kehrwertsatz, weiß aber nicht was mit Konstanten geschieht.

n * log(n)/ n*log(n) * log(log(n))
(n/log_n(e)) // n*log(n) * log(log(n)) -> n / (log_n(e) * n*log(n) * log(log(n))
-> 1/ (log_n(e) *log(n) * log(log(n)) für n-> unendlich konvergiert dies gegen 0

Kann ich damit sagen, dass n*log(n) * log(log(n)) schneller steigt als n * log(n) ?

das passt doch. f € Omega(g) heißt doch, dass f für hinreichend große n größergleich g.

Ahh okey, ich dachte das würde bedeuten, dass es praktisch gleich groß ist.
Anders ausgedrückt bedeuted f € Omega(g), dass es ab einem n0 für alle n f schneller steigt als g.

Da man es hier immer mit Grenzwerten zu tun hat, ist selbst eine in der Praxis nutzlose Aussage über Algorithmen, wo f = 10^999999999*x und g=x^2 aussagt, dass f=O(n) und g=O(n^2) ist (aber eben mit einem sehr hohen x(0)) trotzdem gerechtfertigt, da es eben einen Punkt gibt ab dem g immer größer als f ist, egal wie weit weg der ist, oder wie steil f anfangs ansteigt.

Ja, das ist mir schon klar, vor allem der Unterschied zwischen linear und quadratischer Steigung.
Nur ist es doch auch nicht gerade korrekt einfach davon auszugehen, dass das n maximal ist oder?
Wenn ich einen Algorithmus habe bei dem ich weiß, dass es nie mehr als 1000 bis 100000 n gibt, dann gibt es doch trotzdem die Möglichkeit, dass n^2 die bessere Wahl ist, weil der andere für kleine n wesentlich schneller steigt.

Es existiert eine Konstante c und ein gewisser "Startwert" x(0) für die gilt: Ab dem "Startwert" x(0) sind alle Funktionswerte kleiner/gleich einer linearen Funktion mit Steigung c.

Hmm, verstehe ich noch nicht so ganz...
Heißt das so viel wie, dass es ein n0 gibt ab dem die Funktion f schneller wächst als g für alle n>n0 ? Okay, dass kann es nicht sein, steht ja schon in der Definition.
Was ist da mit linearer Steigung gemeint? Was wenn ich jetzt eine kubische habe?

Nochmal, zu den Landau-Symbolen...
Wenn ich einen Algorithmus habe und ich muss für den möglichst genau die Komplexität angeben.
Das heißt doch, dass ich einfach nur Big Theta(algo) angeben muss? Das ist dann doch egal, dass ich keine zweite Funktion habe zum "abgleichen"?

PS:Ich habe mal nen Link gehabt bei dem die Aufzeichnungen von einer Algorithmen VO vorhanden waren, ich glaube der Vortragende war der Cormen. Hätte den Link zufällig jemand?

 

[maxwell-cs]

mangels zeit gehe ich mal nur auf einen kleinen teil ein:

Hmm vielleich verstehe ich deine Aussage nicht richtig...
Aber es wurde am Anfang definiert, dass log zur Basis 2 und ln zur Basis e ist.

es ist richtig, dass log(n) und ln(n) verschiedene funktionen sind.
allerdings kann man, wie du sicher weißt, logarithmen zur einen basis durch logarithmen zu einer anderen basis ausdrücken:
log(n) = ln(n)/ln(2)

ln(2) ist konstant, daher
log(n) in Theta(ln(n))

 

[Sukrim]

Hmm vielleich verstehe ich deine Aussage nicht richtig...
Aber es wurde am Anfang definiert, dass log zur Basis 2 und ln zur Basis e ist.

ld(n) = ln(n)/ln(2) = c * ln(n)

Logarithmen solltest du dir da wohl nochmal anschauen...
C bedeutet in diesem Fall nur, dass es einen konstanten Faktor gibt (im vorliegenden Fall 1/ln(2) ). Einfach mal 1000 Werte von 3 versch. Logarithmen in Excel plotten macht das Ganze dann auch grafisch verständlich.


Das mit den unterschiedlichen Abschnitten hast du genau richtig erkannt, gerade deswegen muss man aufpassen sich nicht verleiten zu lassen "das wächst eh viel schneller" zu denken und dann falsch einzusortieren. Bei O-Notation geht es nicht um konkrete Probleme oder was jetzt bei n zwischen 1000 und 1 Million sinnvoll ist, sondern NUR um n --> unendlich. Auch eine noch so kleine Kommastelle bei einer Potenz (f=n^2, g=n^2,00000000001) wird sich im unendlichen auswirken und ist daher bei der Berechnung relevant. In der Praxis ist das natürlich anders, dort kannst du dann ja auch konkrete n oder eben Bereiche betrachten. Trotzdem aufgepasst, viele Beispiele sind oft so gestellt, dass man intuitiv/mit Ausprobieren erstmal daneben liegt.

Es existiert eine Konstante c und ein gewisser "Startwert" x(0) für die gilt: Ab dem "Startwert" x(0) sind alle Funktionswerte kleiner/gleich einer linearen Funktion mit Steigung c.

Hmm, verstehe ich noch nicht so ganz...
Heißt das so viel wie, dass es ein n0 gibt ab dem die Funktion f schneller wächst als g für alle n>n0 ? Okay, dass kann es nicht sein, steht ja schon in der Definition.
Was ist da mit linearer Steigung gemeint? Was wenn ich jetzt eine kubische habe?

Linear heißt y = c * x (oder eben O(n)) - eine gerade Linie eben. Kubische Steigung wäre O(n³), quadratische wäre O(n²). Verdoppelt sich dein n bei einer linearen Funktion, verdoppelt sich eben auch das Ergebnis. Bei einer kubischen Steigung würde sich das Ergebnis kubisch erhöhen.

Nochmal, zu den Landau-Symbolen...
Wenn ich einen Algorithmus habe und ich muss für den möglichst genau die Komplexität angeben.
Das heißt doch, dass ich einfach nur Big Theta(algo) angeben muss? Das ist dann doch egal, dass ich keine zweite Funktion habe zum "abgleichen"?

PS:Ich habe mal nen Link gehabt bei dem die Aufzeichnungen von einer Algorithmen VO vorhanden waren, ich glaube der Vortragende war der Cormen. Hätte den Link zufällig jemand?

Einfach mal das Theta von einem Algorithmus aus dem Ärmel schütteln ist leider nicht so einfach... wenn du das aber hast/kannst, dann bist du fertig, ja - es gibt ja dann sowohl eine obere und eine untere Schranke.

https://www.google.com/search?q=cormen+algorithm+lecture - führt zu einem MIT Kurs zumindest, vielleicht meinst du den?

 

[Kuma]

ld(n) = ln(n)/ln(2) = c * ln(n)

Ahh, den Basiswechselsatz kenne ich schon..
Das heißt dann:

n*log(n) -> n * ln(n)/ ln(2) ? Und da ln(2) eine Konstante ist, wirkt sich praktisch nur noch n* ln(n) aus und damit ist n *log(n) und n*ln(n) in der gleichen Komplexität?

Linear heißt y = c * x (oder eben O(n)) - ein

Ich verstehs zwar nicht,.... aber auf Deutsch gesagt, "nimm einfach irgendeinen Wert größer 0" ? (Warum auch immer...)

Einfach mal das Theta von einem Algorithmus aus dem Ärmel schütteln ist leider nicht so einfach... wenn du das aber hast/kannst, dann bist du fertig, ja - es gibt ja dann sowohl eine obere und eine untere Schranke.

Okay, dann mal so:
f= n^2 * n^(5/2) g= n^2 * (log(n)^17.5)^(1/2)
Hier wird vermutlich f schneller wachsen als g?
Also, noch immer f€ O(g)

Oder ist dass schon bei Theta(g), weil es sieht ja so aus, als ob es gleichwertig wäre, ich bin mir nur nicht wegen dem log sicher.
n^(1/5)* n^2= n^(2/5) ; n^2 * log(n)^8,75

Wenn ich mir das jetzt so anschau, ist doch n^2/5 schon fast wieder n also, doch f€O(g)