名古屋大学 情報学研究科 情報システム学専攻 2021年8月実施 専門 問3

Author

祭音Myyura

Description

自然数の有限列のうち、含まれている要素が重複しないものを考える。 そのような列 に含まれる要素のうちで 番目に小さい数（小さい方から数えて 番目の数）を求める再帰的アルゴリズム select（図1）について以下の問いに答えよ。 なお、 は有限列 の要素数を表し、 は天井関数を表す。 天井関数は引数として受け取る実数 に対して、 以上の最小の整数を返す。 さらに、有限列 の中位数は の中で 番目に小さい要素とする。

(1) を以下の列、 を とする。

• (a) このような に対して図 1 の手順の 1. から 5. を順に実行したときに求められる手順の中の列 、自然数 、列 を示せ。なお、列 の要素の並び順についてはアルゴリズムでは言及していないので、解答では並び順を問わない。

• (b) このような に対して select(,) を実行したときの出力を答えよ。

(2) とし、 を の倍数としたときに列 に含まれる得る要素の数の最小値と最大値それぞれをnを用いた式で表せ。

(3) とする。図 1 の手順において、2. における列 を得る操作、5. における列 を得る操作の最大時間計算量をそれぞれ とする。このとき、select(,)（ただし、 ）を実行したときの最大時間計算量をオーダー記法で示せ。解答では でない を用いること。

(4) 以下の整列アルゴリズムを考える。

(a) バブルソート        (b) マージソート        (c) ヒープソート
(d) クイックソート      (e) 挿入ソート          (f) バケットソート

(a)〜(f) のうち、入力として与えられる列の要素数を としたときに以下の条件をすべて満たすものを1つ選択せよ。

• 最大時間計算量が である。
• 図 1 のアルゴリズムを利用することで最大時間計算量を に改善できる。

---

再帰的アルゴリズム select

入力 重複する要素を持たない自然数の有限列 、正整数 （ただし、）

出力 列 に含まれる要素のうちで 番目に小さいもの

手順

1. を とする。
2. 列 を先頭から順に要素5つずつの列 に分ける。つまり、列 から列 を順に連結すると列 に一致する。さらに、列 それぞれに含まれる要素数は5であり、 が の倍数ではないときに列 の要素数は5に満たない。
3. を列 それぞれの中央値からなる列とする。なお、列 の要素の並び順は先頭から順に列 の中央値が並んでいるとする。
4. を列 の中央値、すなわち、select(, ) の返り値とする。
5. 列 を以下を満たす列とする。

6. のときは を返して終了し、そうでないときは次に進む。
7. のときは select(, ) の返り値を返して終了し、そうでないときは次に進む。
8. select(, ) の返り値を返して終了する。

---

図 1: 番目に小さい要素を求めるアルゴリズム

Kai

図１の再帰的アルゴリズム select は「中央値の中央値 (median of medians)」と呼ばれ、クイックセレクトに基づく選択アルゴリズムである。

(1)

(a)

S = [11, 12, 16, 33, 2, 18, 39, 15, 21, 7, 37, 29, 40, 6, 25, 27, 14, 4, 35, 28, 22, 20, 17, 3, 1]

M = [12, 18, 29, 27, 17]

x = 18

A = [11, 12, 16, 2, 15, 7, 6, 14, 4, 17, 3, 1]

(b)

15

(2)

個の小配列に分割した時、その小配列のうち半数 ( 個) の小配列では、各小配列の中央値が の値（中央値の中央値）以下である。

また、各小配列の中には、必ず各中央値以下である要素が 個存在する。 よって、全体としては、 個の要素が の値以下である。

同様に、もう半数の小配列には、 の値以上の要素が少なくとも 個以上存在するはずなので、全体としては、 個の要素が の値以上である。

従って、列 に含まれ得る要素の数の最大値が であり、最小値は ( 自身を除く) である。

(3)

（ を の倍数としたときの計算量を証明する。一般的の場合は、CLRS を参照してください。）

select(, ) の最大時間計算量を とすると、 が満たすことを の大きさに関する帰納法で示す。

が十分大きいとき、(2) より

であり、 とおくと、

であるので、 がわかる。

(4)

(d) クイックソート