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

标签：

• Nagoya-University
• Median-of-Medians

Author

祭音Myyura

Description

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

(1) $S$ を以下の列、$k$ を $10$ とする。

$$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$$

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

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

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

(3) $n = |S|$ とする。図 1 の手順において、2. における列 $G_1, \ldots, G_N$ を得る操作、5. における列 $A, B$ を得る操作の最大時間計算量をそれぞれ $O(n)$ とする。このとき、select($S$,$k$)（ただし、$0 < k \leq n$ ）を実行したときの最大時間計算量をオーダー記法で示せ。解答では $|S|$ でない $n$ を用いること。

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

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

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

• 最大時間計算量が $O(n^2)$ である。
• 図 1 のアルゴリズムを利用することで最大時間計算量を $O(n \log n)$ に改善できる。

---

再帰的アルゴリズム select

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

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

手順

1. $N$ を $\lceil \frac{|S|}{5} \rceil$ とする。
2. 列 $S$ を先頭から順に要素5つずつの列 $G_1, \ldots, G_N$ に分ける。つまり、列 $G_1$ から列 $G_N$ を順に連結すると列 $S$ に一致する。さらに、列 $G_1, \ldots, G_{N-1}$ それぞれに含まれる要素数は5であり、$|S|$ が $5$ の倍数ではないときに列 $G_N$ の要素数は5に満たない。
3. $M$ を列 $G_1, \ldots, G_N$ それぞれの中央値からなる列とする。なお、列 $M$ の要素の並び順は先頭から順に列 $G_1, \ldots, G_N$ の中央値が並んでいるとする。
4. $x$ を列 $M$ の中央値、すなわち、select($M$, $\lceil \frac{|M|}{2} \rceil$) の返り値とする。
5. 列 $A, B$ を以下を満たす列とする。

$$\{a \mid a \text{ は列 } A \text{ に含まれる要素 }\} = \{y \in S \mid y < x\}$$

$$\{b \mid b \text{ は列 } B \text{ に含まれる要素 }\} = \{y \in S \mid x < y\}$$

6. $|A| = k - 1$ のときは $x$ を返して終了し、そうでないときは次に進む。
7. $|A| \geq k$ のときは select($A$, $k$) の返り値を返して終了し、そうでないときは次に進む。
8. select($B$, $k - |A| - 1$) の返り値を返して終了する。

---

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

出典：名古屋大学 入学試験問題

题目描述

考虑一个元素互不重复的有限自然数序列 $S$。递归算法 select(S,k) 用于求 $S$ 中第 $k$ 小的元素，其中 $|X|$ 表示序列长度，$\lceil r\rceil$ 表示不小于 $r$ 的最小整数；序列的中位数定义为第 $\lceil |X|/2\rceil$ 小的元素。

算法步骤如下。

1. 令 $N=\lceil |S|/5\rceil$，从前到后把 $S$ 分成至多含 5 个元素的组 $G_1,\ldots,G_N$。
2. 组成序列 $M$，其元素依次为各组的中位数；递归求 $M$ 的中位数 $x$。
3. 将 $S$ 中小于 $x$ 的元素组成 $A$，大于 $x$ 的元素组成 $B$。
4. 若 $|A|=k-1$，返回 $x$；若 $|A|\ge k$，递归返回 select(A,k)；否则返回 select(B,k-|A|-1)。

完整算法定义见上文。回答下列问题。

1. 对

   $$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),\quad k=10,$$

   依次执行步骤 1—5，写出序列 $M$、自然数 $x$ 和序列 $A$（$A$ 中元素顺序不限）；并求 select(S,10) 的输出。

2. 令 $n=|S|$ 且 $n$ 为 10 的倍数，用 $n$ 表示序列 $A$ 可能包含的元素数的最小值与最大值。

3. 假定分组以及构造 $A,B$ 的操作均为 $O(n)$，求 select(S,k) 的最坏时间复杂度。

4. 在冒泡排序、归并排序、堆排序、快速排序、插入排序、桶排序中，选择一种最坏复杂度原为 $O(n^2)$，但利用该 select 算法选取枢轴后可改进为最坏 $O(n\log n)$ 的排序算法。

Kai

図１の再帰的アルゴリズム select は「中央値の中央値 (median of medians)」と呼ばれ、クイックセレクトに基づく選択アルゴリズムである。以下では、$|S|=1$ なら唯一の要素を直ちに返す基底ケースを用いる。

(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)

$m=n/5$ とおくと $m$ は偶数で、$x$ は $M$ の第 $m/2$ 番目の要素である。

$x$ より小さい中央値をもつ $m/2-1$ 組から各3個、$x$ の組から2個が $x$ 未満なので、

$$|A|_{\min}=3\left(\frac m2-1\right)+2=\frac{3n}{10}-1.$$

一方、$x$ より大きい中央値をもつ $m/2$ 組から各3個、$x$ の組から2個が $x$ より大きい。したがって、

$$|A|_{\max}=n-1-\left(\frac{3m}{2}+2\right)=\frac{7n}{10}-3.$$

(3)

$n$ が任意の正整数の場合も、各組の要素数は高々5なので、組の中央値の計算と分割には $O(n)$ 時間を要する。 $N=\lceil n/5\rceil$ 個の中央値から $x$ を選ぶ。最後の不完全な組と $x$ を含む組を除けば、$x$ の各側に少なくとも $\lfloor N/2\rfloor-2$ 個の完全な組がある。その各組は少なくとも3個の要素を対応する側に保証する。したがって、選択を再帰する側の要素数は高々 $7n/10+O(1)$ である。

最悪時間計算量 $T(n)$ は、ある定数 $a,b>0$ により

$$T(n)\le T(\lceil n/5\rceil)+T(\lfloor7n/10+b\rfloor)+an$$

を満たす。十分大きい $n$ では2つの再帰引数の和は $0.95n$ 以下となる。小さい $n$ の基底ケースを覆い、かつ $c\ge20a$ となるように $c$ を選べば、強い帰納法により

$$T(n)\le0.95cn+an\le cn$$

を得る。よって $T(n)=O(n)$ であり、分割の $\Omega(n)$ と合わせて $\boxed{T(n)=\Theta(n)}$ である。

(4)

(d) クイックソート

線形時間の選択で真の中央値をピボットとすれば、各部分列は高々 $\lceil(n-1)/2\rceil$ 要素となるため、クイックソートの最悪計算量は $O(n\log n)$ となる。