東京工業大学 情報理工学院 数理・計算科学系 2018年8月実施 午前 問C

标签：

• TITech
• Binary-Search
• Algorithm-Complexity

Author

祭音Myyura

Description

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

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) ☆ の行の代入文を

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) ☆ の行の代入文を

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

题目描述

数组 d[0], d[1], ..., d[n-1] 中存放 $n$ 个互不相同并按升序排列的整数。把下列搜索伪代码称为 BinSearch：

def search(k, a, b)         # 返回满足 a ≤ i ≤ b 且 d[i] = k 的 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$，否则返回 $-1$。令 $\operatorname{steps}(k,n)$ 表示此次计算中星号行执行的总次数，也就是 search 的总调用次数。例如，当数组为 {30,50} 时，

$$\operatorname{steps}(30,2)=1,\qquad \operatorname{steps}(40,2)=2.$$

定义

$$\operatorname{max\_steps}(n) =\max_{k\in\mathbb Z}\operatorname{steps}(k,n).$$

它是搜索 $n$ 个元素时的最坏步数，只依赖于 $n$，与数组内具体整数无关。

1. 求 BinSearch 的 $\operatorname{max\_steps}(15)$。

2. 把星号行改为

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

   即 i := b，所得算法称为 UniSearch。求其 $\operatorname{max\_steps}(10)$。进一步，当数组为 {0,2,4,6,8,10,12,14,16,18} 时，给出一个满足 $\operatorname{steps}(k,10)=\operatorname{max\_steps}(10)$ 的整数 $k$。

3. 把星号行改为

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

   所得算法称为 DecSearch。求其 $\operatorname{max\_steps}(10)$；对第 2 问的同一数组，再给出一个达到该最坏步数的整数 $k$。

4. 定义

   • $\operatorname{bin}(n)$：BinSearch 的 $\operatorname{max\_steps}(n)$；
   • $\operatorname{uni}(n)$：UniSearch 的 $\operatorname{max\_steps}(n)$；
   • $\operatorname{dec}(n)$：DecSearch 的 $\operatorname{max\_steps}(n)$。

   分别用 $O(\cdot)$ 表示三者的增长阶，并简要说明依据。

5. 从“严格大于”“严格小于”“等于”中分别选择正确短语填入：

   • $\operatorname{bin}(n)$ 的阶 $\boxed A$ $\operatorname{uni}(n)$ 的阶；
   • $\operatorname{bin}(n)$ 的阶 $\boxed B$ $\operatorname{dec}(n)$ 的阶；
   • $\operatorname{uni}(n)$ 的阶 $\boxed C$ $\operatorname{dec}(n)$ 的阶。

考点

• 二分搜索：根据每次选择中点后搜索区间的缩减比例，计算有限规模下的最坏递归深度。
• 非对称划分搜索：分析选择右端点或靠近左端点的位置时，哪一支产生最长递归链，并构造达到最坏情形的查询值。
• 渐近复杂度比较：由最坏区间长度的递推关系分别求对数阶或线性阶，并比较三种算法的增长级别。

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) のオーダー よりも真に大きい.