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

20

■

2

章 アルゴリズムの数学

はないかと思う人もいるだろう。そうしてもあまり情報は追加されない。まるで、

5

分の仕事に要する時間について、せいぜい

1

週間で済む、というようなものだ。

本書では、アルゴリズムの分類を実際に一番近いものを使う。

計算量理論では、別の表記Θ

(f(n))

を使う。これは上限と下限の

2

つの概念を

使って、厳密な限界を示す。すなわち、下限がΩ

(f(n))

、上限が

O(f(n))

と同じ分

類

f(n)

で決定されるということだ。本書では、広く受け入れられ（より非公式な）

O(f(n))

を使って説明と分析を行う。アルゴリズムの振る舞いを論じるときには、

O(f(n))

と示したアルゴリズム分類よりも正確な

f'(n)

がないことを保証する。

2.4

 性能分類

サイズ

n

の入力データに対する性能でアルゴリズムを比較するという、この方法

論は、アルゴリズム比較のためにこの半世紀で開発された標準的な手法である。こ

うすることによって、入力のサイズ

に対するアルゴリズムの必要実行時間を評価す

ることができ、ある自明でないサイズの問題について、どのアルゴリズムがスケー

ルして解くことができるかを決定できる。性能評価の第二の形式は、アルゴリズム

がどれだけメモリまたはストレージを必要とするかである。この問題に関しては、

必要に応じて個別のアルゴリズムで扱うことにする。

本書では次のような性能分類を使う。これらは、性能の高いものから低いものへ

と並んでいる。

●

定数（

constant

）：

O(1)

●

対数（

logarithmic ...