Skip to content

東京工業大学 情報理工学院 数理・計算科学系 2019年度 午前 問C

Author

祭音Myyura

Description

配列 d[0], d[1], ... , d[n−1] には n 個の相異なる整数が昇順で入っているとする． 探索アルゴリズムを記述した次の擬似コードを BinSearch と呼ぶ．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def search(k, a, b)         # a ≦ i ≦ b かつ d[i] = k となる i を返す.
                            # そのような i が無い場合は -1 を返す.
    i := a + ((b - a) / 2)  # ☆
    if (d[i] == k)
        return i
    else if ((k < d[i]) && (a < i))
        return search(k, a, i-1)
    else if ((d[i] < k) && (i < b))
        return search(k, i+1, b)
    else
        return -1
    end
end

ただし ☆ の行中の / は切り捨てで商を求める演算である． 与えられた整数 k に対して search(k,0,n−1) を実行すると，d[i] = k となる i が存在する場合はその i が返され，存在しない場合は −1 が返される． search(k,0,n−1) の計算の中で ☆ の行が実行される総回数（つまり search が呼び出される総回数）を steps(k, n) と表記する． たとえば配列 d が {30,50} のとき steps(30, 2) = 1 であり（なぜなら search(30,0,1) だけが呼び出される）steps(40, 2) = 2 である（なぜなら search(40,0,1) と search(40,1,1) が呼び出される）． max_steps(n) = \(\max_{k \in Z}\)(steps(k, n)) と定義する． これはこのアルゴリズムで n 個の要素の中から探索をする際の最悪ステップ数である． max_steps(n) の値は n にだけ依存して d[0], d[1], ... , d[n−1] の値には依存しない．

(1) max_steps(15) の値を書け．

(2) ☆ の行の代入文を

1
i := a + ((b - a) / 1)

（これは i := b に等しい）に変更した擬似コードを UniSearch と呼ぶ．UniSearch における max_steps(10) の値を書け． さらに配列 d が {0,2,4,6,8,10,12,14,16,18} のとき，steps(k, 10) = max_steps(10) となる k の値をひとつ書け．

(3) ☆ の行の代入文を

1
i := a + ((b - a) / 10)

に変更した擬似コードを DecSearch と呼ぶ． DecSearch における max_steps(10) の値を書け． さらに配列 d が上記と同じとき，steps(k, 10) = max_steps(10) となる k の値をひとつ書け．

(4) ３つの関数 bin, uni, dec を次のように定義する．

  • bin(n) = BinSearch における max_steps(n).
  • uni(n) = UniSearch における max_steps(n).
  • dec(n) = DecSearch における max_steps(n).

これらそれぞれの関数をオーダー記法 \(O(\cdot)\) で表せ．さらにそれを求めた根拠を簡潔に説明せよ．

(5) 次の \(\boxed{A} , \boxed{B} , \boxed{C}\) に入る正しい語句を「よりも真に大きい」「よりも真に小さい」「と等しい」の中からそれぞれ選べ。

  • bin(n) のオーダーは uni(n) のオーダー \(\boxed{A}\).
  • bin(n) のオーダーは dec(n) のオーダー \(\boxed{B}\).
  • uni(n) のオーダーは dec(n) のオーダー \(\boxed{C}\).

Kai

(1)

  • max_steps(15) = 4

(2)

最悪の場合、要素を大きい順に1つ残らず調べる。

  • max_steps(10) = 10
  • k = 0

(3)

\(b - a <= n - 1 - 0 < n = 10\) なので、\(i = a + ((b - a) / 10) = a\) となる。

よって、(2) と同じに、最悪の場合、要素を小さい順に1つ残らず調べる。

  • max_steps(10) = 10
  • k = 18

(4)

\[ \begin{aligned} \text{bin}(n) &= \text{bin}\left(\frac{n}{2} \right) + O(1) \Rightarrow \text{bin}(n) = O(\log n) \\ \text{uni}(n) &= \text{uni}(n-1) + O(1) \Rightarrow \text{uni}(n) = O(n) \\ \text{dec}(n) &= \text{dec}(\frac{9n}{10}) + O(1) \Rightarrow \text{dec}(n) = O(\log n) \end{aligned} \]

(5)

  • bin(n) のオーダーは uni(n) のオーダー よりも真に小さい.
  • bin(n) のオーダーは dec(n) のオーダー と等しい.
  • uni(n) のオーダーは dec(n) のオーダー よりも真に大きい.