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

■

9

2

章

 

アルゴリズムの数学

アルゴリズムを選ぶときに一番重要なのは、完了に要する時間である。アルゴリ

ズムの期待計算時間を特徴付けることは、本質的に数学の作業となる。本章では、

この時間予測に関わる数学ツールを示す。この章を読めば、本書だけでなく、アル

ゴリズムを記述する他の文献で使われるさまざまな数学用語がわかるようになるは

ずだ。

2.1

 問題インスタンスのサイズ

問題インスタンスとは、問題に対する具体的な入力データセットのことを指す。

ほとんどの問題において、問題インスタンスのサイズが増えるにつれて実行時間が

増加する。同時に、（圧縮技法を用いた）大幅に圧縮した表現では、プログラム実行

が不必要に遅くなることがある。問題インスタンスの最適な表現を定義することは、

驚くほど難しい。その理由は、問題が実世界で起こっているので、コンピュータプ

ログラムで解くために、適切な表現に変換しなければならないからだ。

アルゴリ

ズムを評価するとき、問題インスタンスの符号化がアルゴリズムが効率

的に実装できるかどうかの決定要因とはならないものと仮定できる（と我々は望ん

でいる）。問題インスタンスの表現は、行われる必要がある演算の型や種類だけに

依存すべきだ。効率的なアルゴリズムの設計は、問題を表現するデータ構造を適切

に選ぶことから始まることが多い。

インスタンスのサイズは形式的に定義できないので、インスタンスが一般的に受

け入れられる簡潔な方式で符号化されたと仮定する。例えば、

n

個の整数をソート

するときには、それら ...