跳到主要内容

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

标签：

Author​

GPT-5.6 Sol, 祭音Myyura

Description​

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

(1)​

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

(a) O(n3),(b) Ω(n2),(c) Θ(nlog⁡m),(d) Ω(n),(e) O(log⁡n),(f) O(2n).\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}

なお、原問では (c) だけが Θ(nlog⁡m)\Theta(n\log m) と印字されているが、mm は問題中で定義されていない。

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

  • (ア) サイズ mm の空のハッシュ表に store(x) を実行して新たな値 xx を格納するとき、store(x) の実行時間を漸近的記法（オーダ記法）で表せ。
  • (イ) 次の状態のハッシュ表 (m=15)(m=15) に store(6)、store(15)、store(13) をこの順に実行した。実行後のハッシュ表の状態を図示せよ。
添字01234567891011121314
HH3002302007002510122714
  • (ウ) search(x) の疑似コード中の空欄 a、b にそれぞれ当てはまる適切な条件式を答えよ。

Kai​

(1)​

原問の (c) に現れる mm は未定義である。ここでは文脈上の誤植とみなし、(c) を Θ(nlog⁡n)\Theta(n\log n) と解釈する。

各選択肢を比較する。

h(n)n3=3log⁡2nn2→0,h(n)n2=3log⁡2nn→0,\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,
h(n)nlog⁡n=正の定数,h(n)n=3nlog⁡2n→∞.\frac{h(n)}{n\log n}=\text{正の定数},\qquad \frac{h(n)}{\sqrt n}=3\sqrt n\log_2n\to\infty.

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

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

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

(2)​

(ア)​

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

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

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

(イ)​

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

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

添字01234567891011121314
HH301523132067002510122714

(ウ)​

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

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

となる。

検算​

一時プログラムで線形探査を逐次実行し、挿入位置が順に 6,1,46,1,4、最終表が

[30, 15, 2, 3, 13, 20, 6, 7, 0, 0, 25, 10, 12, 27, 14]

となること、および格納済みの各値と未格納値に対して search の条件が正しく働くことを確認した。

本页目录