4 verschiedenen (Zufalls-)Zahlen
-
Tachyon schrieb:
Ne, die ist schon quadratisch. Das kannst Du auch leicht selbst ausprobieren, mit dem Algo, den drakon hier gepostet hat. Einfach die Iterationen mitzählen und mal mit der Arraylänge spielen. Sofern da kein Bock drin ist, sollten die Iterationen näherungsweise quadratisch zur Arraylänge wachsen.
So, das hat mich nun belastet. Also hab ich mal eine Regression durchgeführt (zwar nur 15 Werte), und das kommt ziemlich gut hin (R2 = 0.98). Scheint also wirklich quadratisch zu wachsen...
Hm, also quadratisch, weil erstens n Mal das Array durchgegangen werden muss und zweitens bei jedem Index vom Anfang an wieder iteriert wird. In diesem Falle wirken sich die zusätzlichen Neuanfänge durch bereits vorhandene Zahlen nicht auf die Komplexitätsklasse auf, nur auf die Dauer des Algorithmus, sehe ich das richtig? Aber dann müssten die Neuanfänge ja von konstanter Dauer sein. Es stimmt schon, wie du sagst, Tachyon, aber wie kann man das erklären? Ich seh da gerade nicht durch...
Tut mir leid, wenn ich über etwas völlig Belangloses diskutiere... (und ja, ich hatte gerade zuviel Zeit :)).