Hallo Leute!
Ich habe mir mal zwei tage Auszeit gegönnt und mir indess "Algorithmen in Perl" von O'Reilly etwas genauer angeschaut.
Dabei ist mir ein Kapitel nicht so ganz klar geworden. Es war dasjenige über die Komplexität eines Algorithmus.
Dargestellt sind viele verschiedene Komplexitätsgrade, wie z.B. die folgenden:

1) O(N)
2) O(logN)
3) O(NlogN)
...

Ich habe keine Ahnung was das beduetet, jedoch habe ich hier im Forum schon einmal einige Beiträge gelesen (pq, Ishka, ptk,... AFAIK), die diese Schreibweise verwendeten. Kann mir jemand erklären, was es damit auf sich hat? O(N), so habe ich gelesen, ist linear. Was bedeutet das für den Programmablauf? Und wieso v.a. gibt es das ganze auch mit Logarithmen?
Wer kann helfen?
Danke! :)

O(N) - ist linear d.h. die Verarbeitung eines Elementes dauert n-Sekunden, die Verarbeitung von zwei Elementen 2n-Sekunden.

O(N^2) is quadratisch d.h. die Verarbeitung von zwei Elementen dauert vier mal solange wie bei einem, bei drei Elmenten dauert es schon neun mal solange usw.

O(log N) ist logarithmisch - die Suche nach dem n-ten Element kann hier in log(n) der Zeit erfolgen.

In dem Buch sind aber ein paar gute Beispiele.

Wieso gibt man das so kompliziert an? Wieso schreibt man die Zeit dann nicht einfach in die Klammer? Und v.a. für was braucht man das?

Jup. Relavant für die Definition ist auch zu wissen, daß konstannte Vorfaktoren egal sind. Zudem sollte man sich genau überlegen, was mit n gemeint ist - meistens die Eingabelänge.

Ein Beispiel, wo man das beides nicht vergessen sollte: der 'schnellste' bekannte Primzahltest geht mit O(n^6). Gemeint ist natürlich die Anzahl der bits und nicht die Zahlengröße. Zudem braucht dieser Test aufm 1GHz-er zum Beweis, daß 13 ne Primzahl ist ca. eine Sekunde. Nichts desto trotz, ist er bei einer 100 000 000 000 000-bit - Primzahl natürlich schneller, als alle anderen bekannten.

Damit du abschätzen kannst wie "gut" ein Algorithmus skaliert. Für kleine Datenmangen ist auch ein O(N^2) okay, aber bei vielen Daten tut das schnell weh. Wenn es also einen Algorithmus gibt, der dieselbe Aufgabe in O(N) erledigt bedeutet das, dass dieser Algo. viel effizienter skaliert.

[E|B

,28.07.2004, 14:16]Wieso gibt man das so kompliziert an? Wieso schreibt man die Zeit dann nicht einfach in die Klammer? Und v.a. für was braucht man das?

Daß das nicht kompliziert ist, bemerkst du, wenn du dich ne Weile damit beschäftig hast.

Weil ne Zeitangabe nichts darüber aussagt, wie lang das dauert, wenn man die Eingabelänge verändert.

Weil das (fast) das einzig relevante ist, wenn man mit größeren Datenmengen hantiert.

OK, was bezeichnet N denn dann genau? Ihr sprecht von Eingabelängen, im Buch wird von Variablen geredet. Meint man damit einfach nur die Anzahl an Werten, die verarbeitet wird?

O(N): linear, es werden N Elemente in O(N) Sekunden abgearbeitet
O(N^K): ??, es werden N Elemente in O(N^K) Sekunden abgearbeitet
O(logN): ??, es werden N Elemente in O(logN) Sekunden abgearbeitet

Ich verstehe die Funktion des Logarithmus' noch nicht ganz. Wieso nimmt man ausgerechnet logN? Man könnte doch auch N/3 oder sonst was nehmen.
Und wie sieht es mit O(NlogN) aus? Fragen über Fragen... ;)

Du kannst bei N einfach von der Anzahl der Werte ausgehen die verarbeitet werden sollen. Du hast nicht die Wahl ob sich ein Algorithmus so oder so verhält. Wenn ein Logarithmus sich logarithmisch (zur Basis 2) verhält brauch er zum verarbeiten von 256 Elementen nur 8 Schritte. Das hast du z.b. beim suchen nach einem Element in einer geordneten Liste (in Abhängigkeit vom gewählten Algo. - du kannst die Liste ja auch linear abklappern.).\n\n

<!--EDIT|Ronnie|1091019084-->

n log n heißt einfach n mal log n

O() ist keine Funktion, sondern eine Klasse (im Prinzip eine Menge), dh. du kannst nicht sagen O() Sekunden. Ein Algorithmus kann halt ein Element dieser Klasse sein. Dadurch weißt du dann, wie er sich verhällt, wenn es viele Eingabewerte werden.

Vielleicht helfen dir ein paar Beispiele weiter:

Ist linear in n (dh. O(n)), bzw. exponentiell in der Eingabelänge (irritierenderweise auch als O(exp n) bezeichnet -- das ist das, was ich meinte mit hinschauen, was gemeint ist)

Ist natürlich quadratisch in n (dh. O(n^2)) -- Eingabelänge lass ich jetzt erstmal weg, um dich nicht weiter zu verwirren

Wobei algo die Komplexität O(n) habe.
Ist natürlich auch Quadratisch, dh O(n^2)

Verständlicher?

@eb: die O-notation beschreibt nicht die laufzeit eines algorithmus,
sondern das laufzeitverhalten. das bedeutet, es beschreibt, wie sich die
laufzeit in abhängigkeit von N verändert.
nehmen wir ein einfaches beispiel:
sub array {
 for (@_) { print "Element: $_\n" }
}
wie lange dieses programm braucht, weiss man nicht. das hängt ja vom rechner
ab und von der anzahl der elemente in @_. nennen wir die anzahl N.

die sub läuft bei N=1 eine bestimmte zeit lang x (wohl sehr kurz für ein
einziges print, aber unbekannt, weil wir den rechner nicht kennen). bei N=2
läuft die sub 2 mal solange, 2x. bei N=3 dreimal, 3x. usw. das heisst, die
laufzeit ist linear zur anzahl der elemente, deswegen O(N).

jetzt folgende sub:
sub array2 {
 for (@_) { print "Element: $_\n" }
 for (@_) { print "Zweiter Durchlauf: $_\n" }
}

auch diese sub hat O(N)! warum? weil die sub ganz sicher zwar länger braucht
als die erste, aber nochmal, hiergeht es um das laufzeitverhalten. bei N=1
haben wir eine bestimmte zeit x, bei N=2 wieder 2 mal x, N=3 3x.
auch hier steigt die laufzeit linear zu N.
klar, die zeit x ist in diesem fall höher als in der ersten sub. aber das
wollen wir ja gar nicht wissen, sondern wir wollen nur wissen, was passiert,
wenn ich mehr Elemente N habe.
man kann hier auch schreiben: O(2N), wenn man einen bezug zur der ersten sub
herstellen will. aber absolut gesehen ist die 2 eine konstante und
vernachlässigbar.

folgende sub:
sub array2 {
 for (@_) {
   for (@_) { print "Innerer Durchlauf: $_\n" }
 }
}
diese sub braucht bei einem element die laufzeit x (das print wird einmal
ausgeführt). bei zwei elementen hsben wir die laufzeit 2*2, also 4. bei drei
elementen ist x=3*3, also 9. aha, also quadratisches laufzeitverhalten, also
O(N*N) = O(N^2)

so hab ich das damals verstanden, als ich es gelernt habe. die meisten
fachbegriffe habe ich wieder vergessen; darin bin ich echt eine niete, aber
ich merk mir zumindest das prinzip, nachdem es funktioniert.