昨日の問題
基本情報技術者試験明けの頭で考えるに、id:margin:20060416:1145198675の最後の命題は「任意のn要素の配列を高々 回の比較でソートできる*1」という命題と同値。
というわけで、先日日本語訳が発売されたThe Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)を立ち読みしてみると、最小比較ソートの項にそれっぽい事が書いてありました。 それによると n = 12 のとき 30 回の比較が必要らしいので前の命題は偽。 ざんねん。
この本欲しいんだけど値段がなぁ。 まあ、そのうち買っちゃうんでしょうけど。
