Ich möchte wissen, ob java.util.Random.next(n) linear mit n skaliert oder eine Konstante ist? Könnte mir jemand dabei helfen oder mir zeigen, wie man die Komplexität bestimmen kann?
Aus der Dokumentation:
Random.nextInt (n) verwendet Random.next () weniger als zweimal im Durchschnitt verwendet es einmal und wenn der erhaltene Wert über dem höchsten Vielfachen liegt von n unterhalb von MAX_INT wird es erneut versucht, andernfalls wird der Wert zurückgegeben modulo n (dies verhindert die Werte über dem höchsten Vielfachen von n unterhalb von MAX_INT, wodurch die Verteilung verzerrt wird), so dass ein Wert zurückgegeben wird, der gleichmäßig im Bereich von 0 bis n-1 verteilt.
Laut den Dokumenten wird java.util.Random.next wie folgt implementiert:
Also ist die Komplexität O (1)
Nebenbei bemerkt: -
Sie können mehrere Tools verwenden, um die Komplexität mit einem Mikro-Benchmark zu messen. Sie können eine Liste über finden hier . Wenn jedoch die Laufzeitkomplexität für Sie wichtig ist, können Sie den Fast Mersenne Twister verwenden (Dies ist ein externer Bibliothek, um die Laufzeitkomplexität zu messen, da Javas Zufallszahlengeneratoren ziemlich schnell, aber statistisch schlecht sind)
Das Javadoc von next erklärt
Die Methode
aktualisiert wirdnextwird durch die Klasse Random implementiert, indem der Seed automatisch auf
(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)und zurückgeben
(int)(seed >>> (48 - bits))
Offensichtlich gibt es in diesen Ausdrücken keine Spur von O (n) -Komplexität.
Laufzeit ist O(1) , wenn dieses Quellcodebeispiel immer noch relevant ist.
Ich glaube, es liegt an Oracles Erklärung, wie sie Zufallszahlen generieren auf dieser Seite .
Eine Instanz dieser Klasse wird verwendet, um einen Pseudozufallsstrom zu erzeugen Zahlen. Die Klasse verwendet einen 48-Bit-Seed, der mit a geändert wird lineare Kongruenzformel. (Siehe Donald Knuth, Die Kunst des Computers Programmierung, Band 2, Abschnitt 3.2.1.)
Tags und Links java time-complexity