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

2.5

 ベンチマーク演算

■

33

最大公約数を計算するためには、さらに優れたアルゴリズムも設計されている。

ただし、そのほとんどは、非常に大きな整数の場合を除いては実用的でない。また、

これまでの分析から、この問題は、さらに効率的なアルゴリズムによって解かれる

可能性がある。

2.4.8

 指数性能

3

つの

0

から

9

を示すダイヤルを順に回す鍵を考えよう。各ダイヤルで

10

個の数

字のいずれかを独立に設定できる。そういう鍵に出会ったが、その組み合わせを知

らないと仮定しよう。

000

から

999

までの

1000

個の組み合わせをそれぞれ調べる

のは手間がかかる仕事だ。この問題を一般化し、鍵に

n

個のダイヤルがあるとする

と、可能性は全部で

10

n

になる。この問題を力任せで解くと、指数性能になる。こ

の場合は指数の底が

10

、つまり

O(10

n

)

になる。多くの場合、指数性能というと底

が

2

のことを指すが、

b

＞

1

のすべての底については指数性能と呼べる。

指

数アルゴリズムは、

n

が小さい値のときだけ実用になる。アルゴリズムによっ

ては、最悪時の振る舞いが指数であるのに、平均時の振る舞いはそう悪くないため

に、実用上は重用されていることがある。線形計画法の問題を解く

シンプレックス

法（

Simplex Method

）が好例である。

2.4.9

 漸近的成長のまとめ

よりよい漸近的成長をするアルゴリズムは、より悪い漸近的成長のアルゴリズム

よりも、実際の定数にかかわらず、結局は実行が速い。実際に優劣が決まる個所は、

実際の定数に基づいて異なるが、その ...