Probability and Computing - makisyuの日記Twitter連携とmixi連携を付けてみた。 はてなブログの使い方を練習しつつ連投する。 例によってこの本 確率と計算 ―乱択アルゴリズムと確率的解析― 作者: Michael Mitzenmacher,Eli Upfal,小柴健史,河内亮周出版社/メーカー: 共立出版発売日: 2009/04/24メディア: 単行本購入: 2人 クリック: 31回この商品を含むブログ (11件) を見る の話の続き。 そういえば。 この本に、バケツソートはある条件下で平均のソートができる、ということが書いてあって面白かった。ソートの下界はなのだが、条件を付ければ線形まで落とせるようだ。詳細はググればすぐに出そうなので書かないけれど、この内容で分割統治の力を再認識した。 分散も分割が基本戦略になると思うのだけれど、分割はいいとしてその統合（MapReduceで言うところのReduce）の実装って実はとても
