アルゴリズムイントロダクション第5章の個人まとめ

前回の続きをやっていきたいと思います。
www.hanachiru-blog.com

今回のテーマは「確率的解析と乱択アルゴリズム」になります。

<br />

確率的解析は確率を用いる問題の解析手法である。

入力分布に関する知識、もしくは入力分布を仮定する必要があり、実行時間の平均を計算してアルゴリズムを解析する。

このように全ての可能な入力に対する実行時間を平均して計算される実行時間を平均実行時間と呼ぶ。

アルゴリズムの確率的解析には指標確率変数が役に立つ。

標本空間Sと事象Aが与えられているとする。この事象Aに関する指標確率変数 $I \{A \}$ を

$I\{A\} = \begin{cases}1 & Aが起こる時\\0 & Aが起こらない時\end{cases}$

と定義する。

例. コインを投げた時に表が出る確率とその期待値
$S = \{ H, T \}, Pr \{ H \} = Pr \{ T \} = 1/2$ のとき、表が出るという事象 $H$ に関する指標確率変数 $X_H$ と定義する。

$X_H = I\{H\} = \begin{cases}1 & Hが起こる時\\0 & Tが起こる時\end{cases}$

期待値は以下の通り。

$E［X_H］ = E［I \{ H \}］ = 1・Pr\{ H \} + 0・Pr \{ T \} = 1/2$

アルゴリズムの振る舞いが入力と乱数生成器が生成する値の両方によって決まる時、アルゴリズムを乱択アルゴリズムと呼ぶ。

アルゴリズムの振る舞いをランダム化する、ランダムな順序を強制することが確率的解析と異なる箇所である。

乱択アルゴリズムの実行時間を解析するときには、乱数生成器が返す値の分布の上での実行時間の期待値をとり、乱択アルゴリズムの実行時間を期待実行時間と呼ぶ。

はなちるのマイノート