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

2.3

 最良、平均、最悪時の分析

■

17

入力集合のサイズ

n

n/4

個の要素がランダムに本来の位置から

4

個分ずれているほぼソートされたデータ

Sort-1

Sort-2

Sort-3

Sort-4

図2-3　ほぼソートされたデータでは Sort-4 が最速

これらの

3

つの場合のアルゴリズム性能を把握していれば、そのアルゴリズムを

自分の抱えている状況で使うべきかどうかの判断ができる。

2.3.1

 最悪時

同じサイズ

n

であっても、アルゴリズムやプログラム内で実行される作業はイン

スタンスによって大きく異なる。ある与えられたプログラムと与えられた

n

におけ

る最悪実行時間とは、最大実行時間、すなわち、サイズ

n

のすべてのインスタンス

についての実行時間のうちの最大のものとなる。

アルゴリズムの最悪時の振る舞いに興味を持つのは、それが最も容易な分析であ

ることが多いからだ。また、状況によってプログラムがどれほど遅くなるかもわか

る。

数学的には、

S

n

をサイズ

n

のインスタンス

s

i

の集合、

t ()

が各インスタンスについ

てアルゴリズムの作業量を測る関数としたときに、最悪時の

S

n

に対するアルゴリズ

ムによる作業量は、すべての

s

i

∈

S

n

に対する

t (s

i

)

の最大値となる。この

S

n

に対す

る最悪時作業量を

T

wc

(n)

で表すと、

T

wc

(n)

の成長率がアルゴリズムの最悪時計算

量を定義する。

最悪時性能をもたらす入力問題を実験的に決定すべく、すべてのインスタンス

s

i