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

互いに異なる $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!$ 通りの並べ方のどれであるかが同様に確からしいとき、比較回数の期待値を求めよ。

互いに異なる $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$ の比較）の回数の期待値を求めよ。

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

$k=1,2,\dots ,6$ の順に、$j=1,2,\dots ,7-k$ の順で $A[j]$ と $A[j+1]$ を比べ、$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

最初の並びは、$7$ 個の数の $7!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる対象の数が $0$ 個または $1$ 個のときは、何もせずに終わる（比較は行わない）。
• 対象の数が $m$ 個（$m\ge 2$）のときは、その $m$ 個の中からピボットを $1$ 個、等しい確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個のそれぞれと $1$ 回ずつ比較し（比較は $m-1$ 回）、ピボットより小さい数の組と大きい数の組に分ける。それぞれの組に対して、同じ手順を繰り返す。

ピボットの選択はすべて互いに独立に行われるものとする。このとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。

相異なる $9$ 個の実数を格納した配列 $A[1],A[2],\dots ,A[9]$ がある。$A$ の要素のうち、小さい方から数えた順位が $3$ 以上 $7$ 以下であるものを「良い要素」とよぶ。良い要素を $1$ つ見つけるために、次の乱択アルゴリズムを使う。

• $1$ 以上 $9$ 以下の整数 $i$ を等確率 $\frac{1}{9}$ で選ぶ。
• $A[i]$ を、それ以外の $8$ 個の要素 $A[j](j\ne i)$ のそれぞれと $1$ 回ずつ比較して、$A[i]$ より小さい要素の個数を数え、$A[i]$ の順位を求める。
• $A[i]$ が良い要素であればアルゴリズムを終了し、そうでなければ最初に戻って $i$ を選び直し、同じことをくり返す。

ここで、各回の $i$ の選び方は互いに独立であり、以前に選んだ位置が再び選ばれることもある。また、各回の比較はその回ごとに改めて $8$ 回行う（以前の比較結果は使わない）。アルゴリズムが終了するまでに行う要素どうしの比較の回数の期待値を求めよ。