アルゴリズムクイックリファレンス 第2版

12.3

 正しいデータ構造を選べ

■

387

分探索

が、問題のサイズを

n

から

n/2

にどう変換したか考えてみよう。

二分探索

は、

探索という作業の持つ繰り返しという性質を利用して、問題に対する再帰的な解を

得ている。

再帰という方法を取らなくても、

2

つの下位問題に分割することで解ける問題も

ある。

凸包走査

は、

2

つの部分凸包（上と下）を構成して合わせることにより、最終

的な凸包を作る。

問題を、同じ入力データに対して、異なった（見たところばらばらな）より小さな

問題の繰り返しに分解できることもある。

フォード

-

ファルカーソン法

は、フローネッ

トワークの最大フローを計算するのに、フローを追加できる増加道を繰り返し見つ

けていく。増加道が見つからなくなったら、元の問題が解けたことになる。選択ソー

トでは、配列の最大値を見つけては、それを配列の右端の要素と入れ替える。

n

回

の繰り返しで配列が整列する。同様に、

ヒープソート

では、ヒープの最大要素を配

列の正しい位置にある要素と入れ替えることを繰り返す。

動的計画法は問題をより小さな問題に分解するが、その性能は

O(n

2

)

もしくは

O(n

3

)

となる。なぜなら、その小さくした問題のサイズは

1

つだけ小さくなってい

るに過ぎず、半分にはなっていないからだ。

表12-2は、

5

章で論じた探索アルゴリズムの比較を示す。これらのアルゴリズム

は、集まりにある要素が含まれているかという基本的な問題に異なるアプローチを

取る。性能分析では、一連の演算に対するならしコストという技法を取る。これに

よ