アルゴリズムと計算量の問題

互いに異なる $8$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[8]$ の最大値と最小値を、次のアルゴリズムで同時に求める。

• 最初に $M\leftarrow A[1]$, $m\leftarrow A[1]$ とする。
• $i=2,3,\dots ,8$ の順に、次の操作を行う。
• まず $A[i]$ と $M$ を比較する。$A[i]>M$ ならば $M\leftarrow A[i]$ とし、この $i$ についての操作を終える（$m$ とは比較しない）。
• $A[i]<M$ ならば、続けて $A[i]$ と $m$ を比較する。$A[i]<m$ ならば $m\leftarrow A[i]$ とする。

配列の並び方は $8!$ 通りのどれも同様に確からしいとする。このアルゴリズムで行われる要素どうしの比較（$A[i]$ と $M$ の比較、$A[i]$ と $m$ の比較）の回数の期待値を求めよ。

互いに異なる $8$ 個の数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の配列はそのまま返す。
• 長さ $2k$（$k$ は正の整数）の配列は、前半 $k$ 個と後半 $k$ 個に分け、それぞれを再帰的にこのマージソートで並べかえたあと、次の「マージ」で $1$ つの昇順の列にまとめる。
• マージ: 昇順に並んだ 2 つの列の先頭どうしを $1$ 回比較し、小さい方を取り出して出力の末尾に加える。これを一方の列が空になるまで繰り返し、空になったら、もう一方の列に残っている数を比較せずにそのまま出力の末尾に加える。

入力の $8$ 個の数の並び方は $8!$ 通りすべてが等確率で現れるものとする。このとき、ソート全体で行われる数どうしの比較回数の期待値を求めよ。

互いに異なる $6$ 個の実数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の列はそのまま返す。
• 長さ $k\ge 2$ の列は、前半の $\lceil k/2\rceil$ 個と後半の残り $\lfloor k/2\rfloor$ 個に分け、それぞれを再帰的に昇順に並べかえてから、次の手続きで併合する。
• 併合の手続き: 昇順に並んだ $2$ つの列 $P,Q$ が与えられたとき、どちらも空でない間は、$P$ の先頭と $Q$ の先頭を $1$ 回比較し、小さい方を取り出して出力の末尾に加える。一方の列が空になったら、もう一方の列に残っている要素を、比較を行わずにそのまま順に出力の末尾に加える。

入力の $6$ 個の数の並び方は $6!$ 通りすべてが等確率で現れるとする。このマージソート全体で行われる要素どうしの比較回数の期待値を求めよ。

互いに異なる $6$ 個の数を並べた配列 $A[1],A[2],\dots ,A[6]$ を、次の挿入ソートで昇順に並べかえる。

$i=2,3,\dots ,6$ の順に、次の操作を行う。$x=A[i]$ とし、$j=i-1$ から始めて、$j\geqq 1$ である間「$A[j]$ と $x$ を比較し、$A[j]>x$ ならば $A[j]$ を $A[j+1]$ に移して $j$ を $1$ 減らす。$A[j]<x$ ならばそこで止める」をくり返す。止まったとき（または $j=0$ になったとき）、$A[j+1]=x$ とする。

ここで、数どうしの比較（$A[j]$ と $x$ の比較）だけを数え、$j\geqq 1$ かどうかの判定は数えない。最初の配列が $6$ 個の数の $6!$ 通りの並べ方のどれであるかが同様に確からしいとき、比較回数の期待値を求めよ。

互いに異なる $5$ 個の数が入った配列から、小さい方から $3$ 番目の数（中央値）を、次の乱択選択アルゴリズム（乱択クイックセレクト）で求める。

• 現在の候補の集合を $X$ とし、最初は $X$ を $5$ 個の数全体とする。また、求めたい順位を $k=3$ とする。
• $X$ の要素が $1$ 個だけなら、それを答えとして終了する（比較は行わない）。
• そうでなければ、$X$ の要素から $1$ つを等確率で選んでピボット $p$ とし、$p$ を $X$ のほかのすべての要素と $1$ 回ずつ比較して、$p$ より小さい要素の集合 $L$ と大きい要素の集合 $R$ に分ける（このとき比較は $|X|-1$ 回行われる）。
• $|L|=k-1$ なら $p$ を答えとして終了する。
• $|L|\ge k$ なら、$X$ を $L$ に置き換えて（$k$ はそのまま）最初の手順に戻る。
• $|L|\le k-2$ なら、$X$ を $R$ に、$k$ を $k-|L|-1$ に置き換えて最初の手順に戻る。

ピボットの選択は毎回独立に行われるものとする。このアルゴリズムが終了するまでに行う比較の回数の期待値を求めよ。