verkettete liste soll nur unikate enthalten.
-
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 ?
-
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=1999000ok, auf das ergebnis komme ich auch.
aaaaaaaaaber:volkard schrieb:
1999000/499500=4.002
das bedeutet doch eine vervierfachung des aufwands und keine 'quadratisierung'
-
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^2macht 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.
-
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_notationIn 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.
-
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ß
-
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.