verkettete liste soll nur unikate enthalten.

was bedeutet denn eigentlich das O(n^2)? hab ich zwar schon öfter gesehen, aber was ist das?

^^laufzeit wächst quadratisch mit der anzahl der zu verarbeitenden daten.

hmm...und welche einheit hat die zeit? sekunden?

also, ich hab mir mal ein paar beispiele für die einfache 'unikat-methode' überlegt:
A,B,C,D sollen die verketteten listen sein.

liste hat zwei elemente A,B:
1 verleich ist nötig.

liste hat drei elemente A,B,C:
3 vergleiche sind nötig.

liste hat vier elemente A,B,C,D:
6 vergleiche sind nötig.

mach ich jetzt nen fehler, oder wo ist das quadratische?

volkard

list n00b schrieb:

hmm...und welche einheit hat die zeit? sekunden?

ja. oder stunden. oder tage. ist egal. das ist ja der witz an der O(n^2)-schreibweise.
O(n^2) sagt dir, daß bei doppelt so vielen daten die laufzeit viermal so groß ist.
O(n^2) sagt dir, daß bei dreimal so vielen daten die laufzeit neunmal so groß ist.

O(n^2) sagt dir aber auch, daß bei tausendmal so vielen daten die laufzeit millionenmal so groß ist.
das sind dann angaben, mit denen du was anfangen kannst. wenn du mit nem tastprogramm und 1000 datensätzen 1.5 sekunden brauchst, ist klar, daß du mit 1000000 datensätzen 1.5 mio sekunden brauchst, das sind 17 tage.
O(n^2)-sachen gehört damit zu den eher langsamen sachen, die tunlichst zu meiden sind, wenn man sich offen lassen will, auch mal mit vielen daten zu hantieren.

list n00b schrieb:

hmm...und welche einheit hat die zeit? sekunden?

keine einheit, sondern relativ zu einem element gesehen. braucht dein O(n^2)-programm z.b. für 1 byte 10ms, dann brauchts für 100 bytes 100 sekunden.

volkard

list n00b schrieb:

also, ich hab mir mal ein paar beispiele für die einfache 'unikat-methode' überlegt:
A,B,C,D sollen die verketteten listen sein.

liste hat zwei elemente A,B:
1 verleich ist nötig.

liste hat drei elemente A,B,C:
3 vergleiche sind nötig.

liste hat vier elemente A,B,C,D:
6 vergleiche sind nötig.

mach ich jetzt nen fehler, oder wo ist das quadratische?

liste hat n elemente
n*(n-1)/2 vergleiche sind nötig.

also
0.5*n^2+0.5*n vergleiche sind nötig.

und jetzt schau mal folgende grenzenabschätzung an:
0.5*n^2 <= 0.5*n^2+0.5*n <= 0.6*n^2
für n>10

es sind also zwischen 0.5*n^2 und 0.6*n^2 vergleiche nötig.
da wir bei O(n^2) so faktoren wie 0.5 und 0.6 eh weglassen, um nicht von sekunden und tagen, bzw von deinem schnellen oder meinem lahmen rechner reden zu müssen, sagen wir n^2.

ah, ok, quadratischer aufwand bei verdopplung der elemente ist gemeint.
gut.

volkard schrieb:

n*(n-1)/2 vergleiche sind nötig.
also
0.5*n^2+0.5*n vergleiche sind nötig.

soweit kann ich das noch nachvollziehen aber dann haperts.
um jetzt mal ein beispiel an den haaren herbeizuziehen:
n = 3, anzahl der vergleiche = n*(n-1)/2 = 32/2 = 3.
n = 6, anzahl der vergleiche = n(n-1)/2 = 6*5/2 = 15.

doppelter aufwand aber 3^2 = 9 und nicht 15
wo ist da mein fehler`?

volkard

list n00b schrieb:

ah, ok, quadratischer aufwand bei verdopplung der elemente ist gemeint.
gut.

volkard schrieb:

n*(n-1)/2 vergleiche sind nötig.
also
0.5*n^2+0.5*n vergleiche sind nötig.

soweit kann ich das noch nachvollziehen aber dann haperts.
um jetzt mal ein beispiel an den haaren herbeizuziehen:
n = 3, anzahl der vergleiche = n*(n-1)/2 = 32/2 = 3.
n = 6, anzahl der vergleiche = n(n-1)/2 = 6*5/2 = 15.

doppelter aufwand aber 3^2 = 9 und nicht 15
wo ist da mein fehler`?

doppelte datenanzahl, vierfacher rechenaufwand.
und 3*4=15
wo ist das problem?

ok, knapp vorbei. aber bei größeren datananzahlen wird die abschätzung besser.
n=1000 adv=499500
n=2000 adv=1999000

1999000/499500=4.002

achso, bei großen n vernachlässigt man das 0.5n wie mir scheint. und aus
0.5 * n^2 macht man 1 n^2 irgendwie.
hmm, irgendwie geschummelt ?

volkard

list n00b schrieb:

achso, bei großen n vernachlässigt man das 0.5n wie mir scheint. und aus
0.5 * n^2 macht man 1 n^2 irgendwie.
hmm, irgendwie geschummelt ?

ja, geschummelt.
aber fein geschummelt.

boah 2 sec! das war ja knapp an einer post-kollision vorbei. *g*

volkard schrieb:

n=1000 adv=499500
n=2000 adv=1999000

ok, auf das ergebnis komme ich auch.
aaaaaaaaaber:

volkard schrieb:

1999000/499500=4.002

das bedeutet doch eine vervierfachung des aufwands und keine 'quadratisierung'

volkard

list n00b schrieb:

das bedeutet doch eine vervierfachung des aufwands und keine 'quadratisierung'

die fläche eines quadrats hängt aucgh quadratisch von der seitenlänge ab.
A=a^2

macht bei doppelter seitenlänge die vierfache fläche.

ok, einigen wir uns auf O ( (n^2)*0.5 ) :), denn sonst komme ich da nicht annähernd ans O dran.

knivil

Bevor noch mehr komisches erscheint, hier zwei links, die mir google gegeben hat:
http://www.linux-related.de/coding/o-notation.htm
http://en.wikipedia.org/wiki/Big_O_notation

In dem O steckt normalerweise eine beliebige Konstante (grob gesagt), also alle Programme die eine Laufzeit von 2*n sind in der Klasse O( n ), aber auch die mit 3.5*n etc.

mazal

Wichtig ist zu verstehen, dass O(f(n)) eigtl. nur in etwa sagt, das n "asymptotisch-proportional" zu f(n) ist. D.h. nur bei genügend großem n, verschwindet der Effekt von den Konstanten und Lower-Order-Terms, die sich in O verstecken. Deswegen kann es durchaus sein, dass für kleine n ein O(n²) auch mal ein O(n log n) outperformt. Also kann man nich sagen pauschal sagen, dass wenn man die Wahl zwischen O(f(n)) und O(g(n)) hat, man f(n) nehmen soll, blos weil f(n) < g(n). Man sollte auch auf das n schauen.

Gruß

mazal

Und nochmal @Topic.

Bist du Dir eigentlich sicher, dass du verkettete Listen haben willst oder nicht etwa Hash-Tables oder so?

mazal schrieb:

Und nochmal @Topic.

Bist du Dir eigentlich sicher, dass du verkettete Listen haben willst oder nicht etwa Hash-Tables oder so?

Neee, gar nicht sicher. Das scheint mir doch zuviel Aufwand mit den Listen. Ich mach das jetzt mit nem Hash-Puffer.