広島大学 先進理工系科学研究科 情報科学プログラム 2018年1月実施 専門科目I 問題6

标签：

• Hiroshima-University
• Merge-Sort

Author

祭音Myyura

Description

Algorithm 1 は、整数列 $a_0, a_1, \ldots, a_{n-1}$ を昇順に整列する。 ただし、列 $Q$ を引数とし、その長さを $|Q|$ とする。 また、列 $Q$ の先頭要素を $\text{head}(Q)$ と表し、$i$ 番目の要素を $Q[i]$ と表す。 $Q$ が空のとき、$\text{head}(Q) = \infty$ とする。 関数 $\text{Delete-head}(Q)$ は $Q$ の先頭要素を削除するものとする。 関数 $\text{Allocate}(L, k)$ は長さ $k$ の列 $L$ を確保するものとする。

(1) 入力列 $21, 1, 26, 45, 29, 28, 2, 9$ に対して、Algorithm 1 を実行したときの列の変化の様子を示せ。 また、この時の比較回数を答えよ。ただし、一方の値が $\infty$ であることが分かっているときの要素の比較は、回数に含めなくてよいものとする。

(2) Algorithm 1 の比較回数が最も多くなるような要素数が $8$ の場合の入力列を挙げよ。

(3) Algorithm 1 の最悪時間計算量を答えよ。また、その理由も説明せよ。

---

Algorithm 1 sorts an integer list $a_0, a_1, \ldots, a_{n-1}$ in ascending order. This algorithm takes a list $Q$ as an argument, and let $|Q|$ be the length of $Q$. Let $\text{head}(Q)$ be the first element of $Q$, and $Q[i]$ be the $i$-th member of $Q$. If $Q$ is empty, $\text{head}(Q) = \infty$. Let $\text{Delete-head}(Q)$ be a function to delete the first element of $Q$. Let $\text{Allocate}(L, k)$ be a function to prepare a list $L$ which size is $k$.

(1) Apply Algorithm 1 to the input list $21, 1, 26, 45, 29, 28, 2, 9,$ and illustrate lists after each operation. In addition, show the number of comparison during the execution. However, do not count the comparison when the on value is $\infty$.

(2) Show an input list such that its size is $8$ and the number of comparison is the biggest in Algorithm 1.

(3) Show the time complexity of Algorithm 1. Explain its reason.

Algorithm1(Q)
    if |Q| > 1 then
        m = |Q| / 2;  // rounded down
        p = |Q| - m;
        Allocate(L1, m);
        Allocate(L2, p);
        for i = 0 to m - 1 do
            L1[i] = Q[i];
        for i = 0 to p - 1 do
            L2[i] = Q[m + i];
        Algorithm1(L1);
        Algorithm1(L2);
        merge(L1, L2, Q);
    end

merge(L1, L2, Q)
    for i = 0 to |Q| - 1 do
        if head(L1) < head(L2) then
            Q[i] = head(L1);
            Delete-head(L1);
        else
            Q[i] = head(L2);
            Delete-head(L2);
        end

题目描述

算法 1 将整数序列 $a_0,a_1,\ldots,a_{n-1}$ 按升序排列。它以序列 $Q$ 为参数，$|Q|$ 表示其长度，$\operatorname{head}(Q)$ 表示首元素，$Q[i]$ 表示第 $i$ 个元素；当 $Q$ 为空时规定 $\operatorname{head}(Q)=\infty$。Delete-head(Q) 删除 $Q$ 的首元素，Allocate(L,k) 分配长度为 $k$ 的序列 $L$。算法 1 的完整伪代码见上文代码块。

1. 对输入序列 $21,1,26,45,29,28,2,9$ 执行算法 1，写出各阶段序列的变化，并给出比较次数。若已知参与比较的一方为 $\infty$，该次比较不计入次数。
2. 给出一个含 $8$ 个元素、能使算法 1 的比较次数达到最大的输入序列。
3. 写出算法 1 的最坏时间复杂度，并说明理由。

考点

• 归并排序：跟踪分治与合并过程，分析最坏输入下的元素比较次数，并由递推关系求最坏时间复杂度。

Kai

(1)

[21, 1, 26, 45, 29, 28, 2, 9]
[1, 21, 26, 45, 29, 28, 2, 9]
[1, 21, 26, 45, 29, 28, 2, 9]
[1, 21, 26, 45, 29, 28, 2, 9]
[1, 21, 26, 45, 28, 29, 2, 9]
[1, 21, 26, 45, 28, 29, 2, 9]
[1, 21, 26, 45, 2, 9, 28, 29]
[1, 2, 9, 21, 26, 28, 29, 45]

number of comparison: 15

(2)

7, 3, 5, 1, 8, 4, 6, 2

the biggest number of comparison: 17

(3)

Let $T(|Q|)$ denote the time complexity of Algorithm 1. Since the time complexity of $\text{merge}(L1, L2, Q)$ is $O(|Q|)$, we have

$$\begin{aligned} T(|Q|) &= 2 T \left( \frac{|Q|}{2} \right) + O(|Q|) \end{aligned}$$

by master-theorem we have

$$T(|Q|) = O(|Q| \log |Q|)$$