mehrere Zufallszahlen

Werbeanzeige

the[V]oid

Alter Hase

Beiträge: 775

Wohnort: Aachen

26.06.2009, 02:56

Zitat von »"Nexus"«

Zitat von »"the[V«

oid"]Ist doch dasselbe, ob man nun einen Container erstellt, diesen mit Zahlen füllt, und diese nach und nach (zufällig) rauspickt, oder ob man Zufallszahlen generiert, und nur solche akzeptiert, die noch nicht akzeptiert wurden O.o

Nein. Wie gesagt macht das einen gewaltigen Unterschied in der Zeitkomplexität, der sich bei grösseren Mengen schnell verheerend auswirken kann.

Beim meiner Methode hast du O(n) für das Mischen und O(1) für das Auslesen. Beim Neu-Generieren hast du O(n) für die Anzahl Zufallszahlen und bei jeder Zufallszahl noch O(n) Abfragen auf bereits vorgekommene, also total O(n^2). Bzw. O(n*log(n)) bei einem Baum.

Ähm... ich stimme dir zu bis auf... O(n) fürs Erstellen PLUS O(n) fürs Abfragen macht immernoch O(n)... oder ist mein Bierpegel grad doch etwas zu hoch?