Zufallspermutation |
| 20.01.2013, 18:54 | PaulVersiegelt | Auf diesen Beitrag antworten » |
| Zufallspermutation Das Mischen von Karten eines Pokerspiels stellt eine zufallige Permutation von 52 Karten dar. Dies entspricht einer Permutation der Menge f1; : : : ; 52g, wobei die Zahlen 1 bis 13 den 13 Karten der 1. Farbe, die Zahlen 14-26 der 2. Farbe, die Zahlen 27-39 der 3. Farbe und die Zahlen 40-52 der 4. Farbe zugeorndet sind. Eine einfache Methode um eine zufallige Permutation von N Karten auf dem Computer zu erzeugen, wird im Folgenden beschrieben. (1) Weisse jeder Karte eine Zahl von 1 bis N zu und notiere die Zahlen in einer Liste (Ausgangsliste). (2) Erzeuge eine leere Ergebnisliste. (3) Ziehe eine zufallige Zahl k zwischen 1 und der Anzahl der Eintrage in der Ausgangsliste. (4) Fuge den k-ten Eintrag der Ausgangsliste in der Ergebnisliste hinzu und streiche ihn anschlieend aus der Ausgangsliste. (5) Wiederhole Schritt 3 und 4 bis die Ausgangsliste keine Eintrage mehr enth alt. (6) Die Eintrage der Ergebnisliste sind nun eine zuf allige Permutation der N Karten. Ich soll dabei die Rechenkomplextät bestimmen. Meine Ideen: Wenn ich mich nicht täusche ist unter Rechenkomplexität Laufzeit gemeint. Meine Idee: k kann höchstens N sein. Da beim zweiten Durchgang es nur noch N-1 Zahlen gibt kann k höchstens N-1 sein. Dies führt man N mal durch. Also würde Die rechenkomplexität N*N-1*N-2*...*2*1 = N! Ist das richtig??? Es ist alle so unsicher. Bräuchte umbedingt Hilfe |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |