verkettete liste soll nur unikate enthalten.

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.