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

2.4

 性能分類

■

21

2.4.1

 定数的振る舞い

本書のアルゴリズムの性能分析においては、しばしば、ある基本的な演算は定数

性能であると主張される。この主張は、特定のハードウェアについて何も述べてい

ないので、演算の実際の性能について絶対的な決定を行うものではない。例えば、

32

ビットの数

x

と

y

が同じ値を持つかどうか比較するのは、

x

と

y

の実際の値にかか

わらず同じ性能だろう。定数的演算は、

O(1)

の性能であると定義される。

2

つの

256

ビットの数を比較する性能はどうだろうか。あるいは、

2

つの

1,024

ビットの数ならばどうか。前もって固定サイズ

k

を指定すれば、

2

つの

k

ビットの数

を定数時間で比較できる。肝心なのは、問題サイズ（すなわち、比較される数

x

と

y

との値）が固定サイズ

k

を超えて大きくならないことである。この

k

の定数倍程度の

作業を定数を無視して

O(1)

と記述する。

2.4.2

 対数的振る舞い

バーテンダーが客に

1

万ドルの賭けを申し出た。「

1

から

100

万までの数を私がま

ず選ぶ。あなたは

20

回試すことができる。そのたびに、低い、高い、当たりと私は

答える。

20

回以内で当てたら

1

万ドルあなたに差し上げる。外れたらあなたが

1

万

ドル払ってください。」読者ならこの賭けに応じるだろうか。応じるべきだ。なぜな

ら、いつも勝てるからだ。表 2-1に、

1-8

までの範囲のシナリオ例を示す。これは、

質問のたびに問題インスタンスのサイズをほぼ半分にする。

表2-1　1-8の数を当てる振る舞いの例

数 1回目予想 2