縮小法

縮小法

前項でやった分割統治法は、大きさの問題をコの問題に分割しようというものでした。
それによって問題がとってもわかりやすく解けたわけですけども、ただ「分割」しているだけなので『述べサイズ（実際に解く問題の大きさ）』は変わらないということです。

縮小法というのは、問題を分割し、一部の見込みない入力を捨て去ることによって問題の述べサイズをも減少させてしまおうという方法です。

定順位要素の抽出

といってもイメージが浮かばないと思うので『与えられた実数の集合の中から番目に小さい実数を抽出』するという問題を例にとって考えてみます。

そのアルゴリズムは以下の通りです。
1.のとき、の要素をソートし、番目の要素を取り出して終了する。
2.のとき
2.1. の要素を5個のグループに分けて、各グループの中から順位3番目のものを取り出します。取り出したものの集合をとおきます。
2.2.
2.3. をより小さいものの集合、に等しいものの集合、より大きいものの集合へ分割する。
2.4. if then ;
　　 else if then ;
　　 else
2.5. return

順を追って説明していきます。
1.について。これはもともと問題が小さいなら素直にソートして頑張ってね、という意味です。
2.以降は問題が大きい場合の方法について考えます。
2.1について、まずを5人グループに分けます。そしてその5人グループの中で成績順に分けて、一番平凡な奴を各グループから持ってきます。この平凡組をと言います。
2.2について、平凡組の人数はなので、中央値はその半分、番目の実数になります。ということでこの平凡組の中の平凡という超平凡野郎をとして再帰的に取り出してきます。
2.3についてはそのままですね。超平凡野郎がおそらく平均点に近いので、それより低い人と高い人に分けます。

これで入力が分割できました。
例えば（つまり250番目に低い奴を取ってこいという問題）で、だったとしたら、絶対に目的のやつがいるはずですね。
ですのでこの集合だけをまた再帰的に調べていこうというわけです。これが2.4のやっていることです。

このアルゴリズムは「余計なことをしない」という方法が上手くいっているのでのアルゴリズムになっています。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。