4 verschiedenen (Zufalls-)Zahlen
-
Tachyon schrieb:
O(2x)?
Ich denke, das ist die Komplexitätsklasse für exponentielles Wachstum, oder? Man schreibt ja auch O(n), wenn die Anzahl Operationen 35*n + 7 beträgt...
Okay, n wäre vielleicht besser gewesen als x... Ist es das, was du meinst?
-
So wie ich das sehe, ist die Komplexität O(n2). Wenn es blöd läuft, hat man eine Endlosschleife.
-
Tachyon schrieb:
So wie ich das sehe, ist die Komplexität O(n2). Wenn es blöd läuft, hat man eine Endlosschleife.
Jo, klar, ich wollte ihm ja nur zeigen, wie das mit seinem Ansatz in etwa geht.. Einen besseren Vorschlag habe ich ja schon längst gemacht..;)
@Nexus:
5 Minuten sind nicht soo viel..
-
Hm... Tut mir leid, wenn ich was Falsches erzählt habe.
Quadratisch würde Sinn machen, da ja n Mal eine Zufallszahl erzeugt wird und jeweils die vorherigen Elemente überprüft werden. Jedoch ist das nicht alles.
Macht denn die Tatsache, dass gegen Ende der Sequenz die Wahrscheinlichkeit für eine noch nicht vorhandene Zufallszahl immer kleiner wird, nichts aus? Dadurch müssen bei einer bereits vorhandenen Zahl alle Elemente bis dahin noch einmal überprüft werden, was ja einen erheblichen Einfluss auf die Laufzeit hat.
Das war auch meine Überlegung; selbst wenn exponentiell vielleicht nicht stimmt, wächst die Average-Case-Laufzeit mehr als quadratisch. Beim letzten Element hat man beispielsweise nur eine Wahrscheinlichkeit von 1/n, genau die richtige Zahl zu treffen, was sich bei grossen n stark in die Länge ziehen kann.
-
Hmm... Gehört zwar vielleicht nicht mehr zur Ursprungsfrage, aber seid ihr ganz sicher, dass die Laufzeit quadratisch ist? Würde mich schon noch interessieren...
-
Du überprüfst jede Zahl mit jeder anderen. Wie lange das schlussendlich geht ist nicht die Frage. Tachyon hat ja bereits gesagt, dass man durchaus eine "Endlosschleife" hat. Wobei das auch nicht richtig ist. Der Algorithmus kann theoretisch 1000 Jahre laufen, aber ein Ende hat er immer.
-
drakon schrieb:
Du überprüfst jede Zahl mit jeder anderen. Wie lange das schlussendlich geht ist nicht die Frage. Tachyon hat ja bereits gesagt, dass man durchaus eine "Endlosschleife" hat. Wobei das auch nicht richtig ist. Der Algorithmus kann theoretisch 1000 Jahre laufen, aber ein Ende hat er immer.
Woher willst Du das wissen? Wenn Du Pech (bzw. die Menge ausreichend Groß ist) hast, dann hast Du eine sich wiederholende Folge von Zufallszahlen (und irgendwann wird sie sich wiederholen, sofern es sich um die üblichen Pseudozufallszahlen handelt), bei der Du nur Dubletten produzierst. Wenn der Krempel bereits 1000 Jahre durch hat, ist das sogar ziemlich wahrscheinlich.
Das gibt dann eine echte Endlosschleife.
Der Algorithmus für sich genommen hat jedenfalls O(n2). Das sieht man eigentlich ziemlich direkt.
-
Tachyon schrieb:
...
OK. Das hätte ich vlt. mal noch hinschreiben sollen, dass Vorausgesetzt ist, dass es kein PRNG sein sollte. - Hat ja eigentlich nichts mit dem Algorithmus selbst zu tun.
Ansonsten darf hinter rand ja auch sowas stehen:
int rand () { return 2; }
-
Tachyon schrieb:
Der Algorithmus für sich genommen hat jedenfalls O(n2). Das sieht man eigentlich ziemlich direkt.
Naja, das ist wohl mehr oder weniger Übungssache. Mit Zeitkomplexität und Algorithmen kenne ich mich sowieso nicht wahnsinnig gut aus...
Aber ich dachte, die Komplexitätsklasse gebe an, in welchem Mass die Laufzeit wächst, wenn mehr Elemente dazukommen. Und das ist meiner Ansicht nach in diesem Falle mehr als quadratisch, deshalb kann ich es nicht ganz nachvollziehen...
-
Nexus schrieb:
Tachyon schrieb:
Der Algorithmus für sich genommen hat jedenfalls O(n2). Das sieht man eigentlich ziemlich direkt.
Naja, das ist wohl mehr oder weniger Übungssache. Mit Zeitkomplexität und Algorithmen kenne ich mich sowieso nicht wahnsinnig gut aus...
Aber ich dachte, die Komplexitätsklasse gebe an, in welchem Mass die Laufzeit wächst, wenn mehr Elemente dazukommen. Und das ist meiner Ansicht nach in diesem Falle mehr als quadratisch, deshalb kann ich es nicht ganz nachvollziehen...
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.
Man geht ja für die O-Notation nicht vom Worstcase aus. Sonst hätte Quicksort auch nicht O(n log(n)) sondern ebenfalls O(n2).
Ich muss aber gestehen, dass ich das Thema auch immer ziemlich ätzend fand. Inzwischen gehts aber.
-
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 :)).