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

互いに異なる $7$ 個の実数からなる集合を、次の乱択クイックソートで昇順に並べかえる。

• 大きさ $2$ 以上の集合 $S$ を処理するときは、$S$ の要素から $1$ 個をピボット $p$ として等確率で選ぶ。$p$ を $S$ のほかのすべての要素とそれぞれちょうど $1$ 回ずつ比較し、$S$ を $p$ より小さい要素の集合 $S_{-}$ と $p$ より大きい要素の集合 $S_{+}$ に分ける。そのあと、$S_{-}$ と $S_{+}$ をそれぞれ同じ方法で処理する。
• 大きさ $0$ または $1$ の集合を処理するときは、何もしない（比較を行わない）。

ピボットの選択はそれぞれ独立に行うものとする。最初の集合 $7$ 個全体を処理し始めてから終わるまでに行われる比較のうち、小さい方から $3$ 番目の要素がかかわる比較の回数の期待値を求めよ。

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

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

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

互いに異なる $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$ 回行う（以前の比較結果は使わない）。アルゴリズムが終了するまでに行う要素どうしの比較の回数の期待値を求めよ。

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

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

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