名古屋工業大学 工学研究科 情報工学専攻 2018年度 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

• Nagoya-Institute-of-Technology
• Algorithm-Complexity
• Hash-Table
• Linear-Probing-Hashing

Author

GPT-5.6 Sol, 祭音Myyura

Description

題意の要約（暫定）。

次の (1)、(2) の問いに答えよ。

(1)

$h(n)=3n\log_2 n$ とする。以下に示す関数の漸近的評価 (a) から (f) について、$h(n)$ が当てはまるものをすべて選べ。

$$\begin{array}{lll} \text{(a) }O(n^3),&\text{(b) }\Omega(n^2),&\text{(c) }\Theta(n\log m),\\ \text{(d) }\Omega(\sqrt n),&\text{(e) }O(\log n),&\text{(f) }O(2^n). \end{array}$$

(2)

次は、線形探査を用いた開番地法（オープンアドレス法）に基づくハッシュ表の構成および探索のための疑似コードである。

store(x) {
    v <- x mod m;
    while (H[v] != 0) v <- (v + 1) mod m;
    H[v] <- x;
}

search(x) {
    v <- x mod m;
    while (true) {
        if ( a ) return "見つからない";
        if ( b ) return "見つかった";
        v <- (v + 1) mod m;
    }
}

配列 $H[0\ldots m-1]$ はハッシュ表に対応するサイズ $m\ (m>0)$ の配列であり、各要素は $0$ で初期化されているものとする。store(x) を実行することで正整数 $x$ がハッシュ表に格納され、search(x) は実行時点のハッシュ表が $x$ を含むか否かを答える。格納するデータは正の整数であり、その個数は $m-1$ を超えないものとする。次の問いに答えよ。

• (ア) サイズ $m$ の空のハッシュ表に store(x) を実行して新たな値 $x$ を格納するとき、store(x) の実行時間を漸近的記法（オーダ記法）で表せ。
• (イ) 次の状態のハッシュ表 $(m=15)$ に store(6)、store(15)、store(13) をこの順に実行した。実行後のハッシュ表の状態を図示せよ。

添字	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$H$	30	0	2	3	0	20	0	7	0	0	25	10	12	27	14

• (ウ) search(x) の疑似コード中の空欄 a、b にそれぞれ当てはまる適切な条件式を答えよ。

Kai

(1)

(c) の $m$ を $n$ と読む場合をまず考える。

各選択肢を比較する。

$$\frac{h(n)}{n^3}=\frac{3\log_2 n}{n^2}\to0,\qquad \frac{h(n)}{n^2}=\frac{3\log_2 n}{n}\to0,$$

$$\frac{h(n)}{n\log n}=\text{正の定数},\qquad \frac{h(n)}{\sqrt n}=3\sqrt n\log_2n\to\infty.$$

また、$n\log n$ は $\log n$ より速く、$2^n$ より遅く増加する。したがって、成立するものは

$$\boxed{\text{(a), (c), (d), (f)}}$$

である。ただし、印字どおり $m$ を別の変数と読むならば、$m$ と $n$ の関係が与えられていないため (c) の真偽は判定できない。

(2)

(ア)

空表では $H[x\bmod m]=0$ なので、while の反復は生じない。よって実行時間は

$$\boxed{O(1)}$$

である（より厳密には $\Theta(1)$）。

(イ)

• store(6)：$H[6]=0$ なので、添字 6 に格納する。
• store(15)：添字 $0$ は使用済みで、次の添字 $1$ が空なので、添字 1 に格納する。
• store(13)：添字 $13,14,0,1,2,3$ は使用済みで、添字 $4$ が空なので、添字 4 に格納する。

したがって、実行後は次のとおりである。

添字	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$H$	30	15	2	3	13	20	6	7	0	0	25	10	12	27	14

(ウ)

空要素に到達すれば、それより先に $x$ は存在しない。一方、現在の要素が $x$ なら探索成功である。よって

$$\boxed{\mathrm{a}:H[v]=0},\qquad \boxed{\mathrm{b}:H[v]=x}$$

となる。