- 629 名前：デフォルトの名無しさん mailto:sage [2012/06/04(月) 11:37:58.59 ]
- >>621
p.57
O(NlogN)で抑えるなんて言い方は無い。上に抑えられていることをO(NlogN)程度と言う。
訳者はOの定義もΩやΘとの違いも知らないんだろうな。
所要時間の期待値の件も変。普通は所要時間の期待値と言ったら全ての可能な入力に対する期待値の事だが、この意味ではピボットをどう選ぼうが(選択に定数時間しかかけない限り)クイックソートの計算量の期待値はO(NlogN)だ。
ある特定の入力に対する確率的アルゴリズムの計算量の期待値のことを言いたいんだろうが、本文中には決定的アルゴリズムの話しか出て来てないのにいきなりそっちを持ち出すのは変。
p.150
正格評価でも、yesResultとnoResultの両方を評価するなら実装は遅延評価とほとんど変わらないので、この訳注は完全に嘘。片方しか評価したくない場合なら遅延評価の方が手軽に実装できるのは分かるが、二文目で自分で否定してる。
