※ 引述《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