Re: [問題] 隨機排序的問題

看板Fortran作者latinboy (暱稱)時間15年前 (2009/10/20 12:15)推噓2(2推 0噓 2→)

留言4則, 1人參與討論串7/8 (看更多)

※ 引述《sjgau (sjgau)》之銘言： : ※ 引述《mantour (朱子)》之銘言： : : 為什麼要洗這麼多次呀 : 我想，在或然率，機率，統計學裡面， : 有所謂的大數法則。 : 任何事情，一定要樣本空間夠大， : 才能夠顯示出他的意義。 : : 這樣應該就可以了吧 : : ! a(0) ~ a(51) : : for i=0,50 : : 產生一個 i ~ 51 的亂數 : : swap(a(r), a(i)) : : 想像成本來是52個人坐一排 : : 然後重抽一輪新的座號 : 就這個 52個人坐成一排的觀念來討論， : 你的方法是，從 1號到 52號， : 每一個號碼，去抽出一個號碼 n1, : 和 n1 座位的人互換座位。第一個人與1~52的人隨機互換之後第一個位置是誰的機率都是均等 (如果亂數均勻) 所以第二個位置的人與2~52互換之後第二個位置是誰的機率都是均等以此類推... 因此只要排過一次理論上就是隨機均勻的如果不放心重複3次即可演算法複雜度為O(N) : 我的方法是 : 做 52次，每次抽出兩個號碼 n1, n2 : 這兩個人互換座位。每次隨機選2個人互換所以某個號碼連續52次都不被選中的機率為(50/52)^52=0.13 洗完之後大概有7張牌不會動到這在玩牌就叫做洗不乾淨吧?! 第一個方式有7張牌不被動到的機率為(1/52)^7=9.72*10^-13 這第二個方式真的要靠比N大很多的交換次數來彌補 : 效果，應該是差不多。 : 如果要真正的去檢討比較兩個方法的優劣， : 有必要去精通統計學裡面的檢測技巧，不用阿簡單就證明完畢了 : 真正的拿各種檢測方法去評比優劣。 : 但是，有這麼嚴重嗎？ : 以上兩個方法，多做個幾輪， : 52*10輪，不就搞定。 : 所需要的 CPU time, 不超過 0.1秒如果今天要排2000萬筆資料怎麼辦? 第一個方式快速 (每次只要產生一次亂數只要洗N次記憶體存取可預測性高 ) 準確 (數學可證明) 簡單 (程式也沒有比第二個更複雜) 為何不使用?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 202.145.77.21