先日読了。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/02/26
- メディア: 単行本
- 購入: 19人 クリック: 779回
- この商品を含むブログ (103件) を見る
数学ガール再読もあと少し。今回はアルゴリズムの定量評価が話題。よくある検索とソートの速いアルゴリズムのほか、乱択を用いて入力最悪値を統計的に回避する方法を示す。乱択クイックソートの「僕」の証明が難しかった。ミルカさんのインディケーターを使った証明はエレガント。
乱択クイックソートにおいて、要素jとkが比較されるのは高々１回、j
