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

18

■

2

章 アルゴリズムの数学

について計算を行うだけの十分な資源は存在しない。その代わりに、担当者は、与

えられたアルゴリズムの記述から最悪の入力問題を作り出すべく努力するのだ。

2.3.2

 平均時

多数の

n

個の電話をつなげた電話系は、最悪時、

n

2

人が他の

n

2

人に電話をか

けても呼び出しがつながるように設計する必要がある。このシステムなら、過負荷

でクラッシュすることはないが、構築する費用があまりにも高すぎる。実際には、

n

2

人が他の

n

2

人の異なる番号に電話をかけるという確率はあまりにも小さい。さ

らに安価に構築できるシステムを設計して、数学的な道具立てを使って過負荷でク

ラッシュする確率を検討できる。

サイズ

n

のインスタンス集合に対して、各インスタンス

s

i

には

0

から

1

の範囲の

確率を与え、サイズ

n

のインスタンス集合全体での総和が

1

になるように確率分布

Pr{s

i

}

を与える。数学的には、

S

n

をサイズ

n

のインスタンス集合とすると、次の式

になる。

∑

Pr

{

s

i

} ＝

1

s

i

∈

S

n

t ()

によってアルゴリズムによる各インスタンスでの作業を測ると、

S

n

でアルゴリ

ズムの行う平均作業は次のようになる。

T

ac

(n)

＝

∑

t (s

i

) Pr

{

s

i

}

s

i

∈

S

n

すなわち、インスタンス

s

i

での実作業

t(s

i

)

に、

s

i

が実際に入力となる確率を掛け

る。もし

Pr{s

i

}

＝

0

ならば、

t(s

i

)

の実際の値はプログラムによって行われる期待作

業に影響を与えない。

S

n

に対する平均時作業を

T

ac

(n)

で表すと、

T

ac

(n)

の成長