神戸大学 システム情報学研究科 2019年8月実施 専門科目 アルゴリズム・データ構造

标签：

• Kobe-University
• Algorithm-Complexity
• Binary-Heap
• Priority-Queue

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

[1]

アルゴリズムの計算量が $n,m$ に対して次のように表されるとする。$m=n^2$ のとき，各計算量を $n$ に関する $O$ 記法で表せ。

1. $\log m$
2. $n+\log m$
3. $n(n+m)+m\log m$
4. $n^2+m\log m$

[2]

親の値が子の値以上である最大2分ヒープを，根を添字 $0$ とする配列で表す。図2の初期ヒープは

q = [9, 7, 3, 6, 3, 1, 2, 5]

である。次の優先度キュー実装に関して答えよ。バッファあふれ，空のキューからの取り出し，整数の桁あふれは起こらないものとする。

int size = 0;
int q[BUFSIZE];

void enqueue(int v) {
    int k = size++;
    while (k > 0) {
        int j = (k - 1) / 2;
        if (q[j] >= v) break;
        q[k] = q[j];
        k = j;
    }
    q[k] = v;
}

int dequeue() {
    int result = q[0];
    int v = q[--size];
    int k = 0;
    while (1) {
        int j = k * 2 + 1;
        if (j >= size) break;
        if (j + 1 < size) {
            if ([ア] < q[j + 1]) j = j + 1;
        }
        if ([イ] >= q[j]) break;
        q[k] = q[j];
        k = j;
    }
    q[k] = [ウ];
    return result;
}

1. 空欄 [ア]〜[ウ] を埋めよ。
2. 初期ヒープに enqueue(8) を実行した後のヒープを，木または配列で示せ。
3. 初期ヒープに dequeue() を2回実行した後のヒープを，木または配列で示せ。
4. 要素数 $2020$ のヒープを木で表したときの高さを求めよ。高さは根から葉までの距離の最大値とする。
5. 6要素 $[0,0,0,1,1,2]$ をもつ可能なヒープをすべて列挙せよ。

题目描述

1. 在 $m=n^2$ 的条件下，把题给四个复杂度分别化为关于 $n$ 的大 $O$ 记号。
2. 采用父节点值不小于子节点值的最大二叉堆，根的数组下标为 0，初始数组为 [9, 7, 3, 6, 3, 1, 2, 5]。
   1. 补全 dequeue() 的三个空格；
   2. 求插入 8 后的堆；
   3. 求连续删除最大值两次后的堆；
   4. 求 2020 个元素的完全二叉堆的高度；
   5. 枚举多重集合 $[0,0,0,1,1,2]$ 能构成的全部不同最大堆。

Kai

[1]

$m=n^2$ を代入すれば，

$$\begin{array}{c|c|c} &\text{式}&n\text{ に関する計算量}\\ \hline (1)&\log(n^2)&\boxed{O(\log n)}\\ (2)&n+\log(n^2)&\boxed{O(n)}\\ (3)&n(n+n^2)+n^2\log(n^2)&\boxed{O(n^3)}\\ (4)&n^2+n^2\log(n^2)&\boxed{O(n^2\log n)} \end{array}$$

である。

[2]

(1)

下向き調整では，左右の子のうち大きい方を選び，末尾から退避した値 $v$ と比較する。よって

$$\boxed{[\text{ア}]=q[j],\qquad[\text{イ}]=v,\qquad[\text{ウ}]=v}.$$

(2)

8 を末尾に追加し，$6,7$ と順に入れ替える。

[9, 7, 3, 6, 3, 1, 2, 5, 8]
 -> [9, 7, 3, 8, 3, 1, 2, 5, 6]
 -> [9, 8, 3, 7, 3, 1, 2, 5, 6]

したがって

          9
       /     \
      8       3
    /  \     / \
   7    3   1   2
  / \
 5   6

であり，配列は

$$\boxed{[9,8,3,7,3,1,2,5,6]}.$$

(3)

1回目は 9 を取り出し，末尾の 5 を下向きに調整する。

[9,7,3,6,3,1,2,5] -> [7,6,3,5,3,1,2]

2回目は 7 を取り出し，末尾の 2 を下向きに調整する。

[7,6,3,5,3,1,2] -> [6,5,3,2,3,1]

よって最終状態は

        6
      /   \
     5     3
    / \   /
   2   3 1

すなわち

$$\boxed{[6,5,3,2,3,1]}.$$

(4)

高さ $h$ の完全2分木の要素数は

$$2^h\le n<2^{h+1}$$

を満たす。$2^{10}=1024\le2020<2048=2^{11}$ より

$$\boxed{h=\lfloor\log_2 2020\rfloor=10}.$$

(5)

配列順を幅優先順とすると，条件 $q_{\lfloor(i-1)/2\rfloor}\ge q_i$ を満たす相異なる配列は次の4個である。

$$\boxed{ \begin{aligned} &(2,0,1,0,0,1),\\ &(2,1,0,0,1,0),\\ &(2,1,0,1,0,0),\\ &(2,1,1,0,0,0). \end{aligned}}$$

重複要素の交換だけで得られるものは同一のヒープとして数えた。