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

互いに異なる $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!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

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

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

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

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

$k=1,2,\dots ,9$ の順に、各 $k$ について $j=1,2,\dots ,10-k$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

入力の並びは $10!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

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

• 最初に $mx=A[1]$、$mn=A[1]$ とする。
• $i=2,3,\dots ,6$ の順に、次の操作を行う。
• まず $A[i]$ と $mx$ を比較する。$A[i]>mx$ であれば $mx=A[i]$ とし、この $i$ についての操作を終える。
• そうでなければ、$A[i]$ と $mn$ を比較し、$A[i]<mn$ であれば $mn=A[i]$ とする。

$6$ 個の数の並び方は $6!$ 通りすべてが等確率 $\frac{1}{6!}$ で起こるとする。このアルゴリズムで行われる要素どうしの比較の回数の期待値を求めよ。