2013-03-03から1日間の記事一覧

サンプリングのアルゴリズム

n個あるうちからk個取り出したい。R だと sample 関数を使うだけなのだが、その仕組みが気になる。重複を許す場合(with-replacement)は簡単で、1からnまでの一様乱数をk個作るだけ。計算量はO(k)。重複を許さない場合はどうする? ソースコードを見る前に考え…