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

互いに異なる $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$ に置き換えて最初の手順に戻る。

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

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

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

ピボットの選択は毎回ほかの選択と独立に行うものとする。数どうしの比較は上の「ピボットと残りの数との比較」だけで行われるとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。

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

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

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

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

• 並べる対象の個数が $1$ 個以下なら、何もしないで終わる。
• 対象が $m$ 個 $(m\ge 2)$ のときは、その $m$ 個の中からピボットを $1$ 個、等確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個のそれぞれと $1$ 回ずつ比較して、ピボットより小さい数の集まりと大きい数の集まりに分ける（比較は $m-1$ 回）。そのあと、2 つの集まりのそれぞれに同じ手順を行う。
• ピボットの選び方は、毎回それまでの選び方と独立とする。比較回数として数えるのは、ピボットとほかの数との比較だけとする。

このアルゴリズムが終わるまでに行う比較回数の期待値を求めよ。

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

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

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