京都大学 情報学研究科 知能情報学専攻 2019年8月実施 情報学基礎 F2-1

标签：

• Kyoto-University
• Merge-Sort

Author

祭音Myyura

Description

以下の擬似コードで記述された関数 func(A) は数値配列 A を昇順にソートする。 A, B, L, R は数値配列であり、配列のインデックスは $0$ から始まる。 A[x:y] は A[x] から A[y-1] までの部分配列を表し、関数 len(A) は配列 A の長さを返す。 A.append(z) は配列 A の末尾に数値 z を追加し、print(A) は配列 A の内容を出力し、floor(z) は z 以下の最大の整数を返す。 例えば A=[1,2,3] のとき len(A)=3、A[0:2]=[1,2]、A.append(4) により A=[1,2,3,4] となる。 このとき、以下の問いに答えよ。

(1) [空欄 a], [空欄 b], [空欄 c], [空欄 d] にふさわしいコードを答えよ。

(2) func([2,9,5,3,7,0,1,4]) を実行したとき、出力を出力順に答えよ。

(3) このソートアルゴリズムの時間計算量を示し、その根拠を述べよ。

---

func(A) {
    n = len(A)

    if (n == 1) {
        return A
    }

    m = floor(n / 2)
    L = func(A[0:m])
    R = func(A[m:n])

    B = []
    i = j = 0

    while ([空欄 a]) {
        if (i == len(L) and j < len(R)) {
            B.append([空欄 b])
            j = j + 1
        } else if (j == len(R) and i < len(L)) {
            B.append([空欄 c])
            i = i + 1
        } else if ([空欄 d]) {
            B.append(L[i])
            i = i + 1
        } else {
            B.append(R[j])
            j = j + 1
        }
    }
    print(B)
    return B
}

题目描述

下列 func(A) 将数值数组 $A$ 按升序排序。数组下标从 0 开始；A[x:y] 表示从 A[x] 到 A[y-1] 的子数组；len 返回长度；append 在末尾追加；print 输出数组；floor(z) 为不超过 $z$ 的最大整数。

func(A) {
    n = len(A)

    if (n == 1) {
        return A
    }

    m = floor(n / 2)
    L = func(A[0:m])
    R = func(A[m:n])

    B = []
    i = j = 0

    while ([空栏 a]) {
        if (i == len(L) and j < len(R)) {
            B.append([空栏 b])
            j = j + 1
        } else if (j == len(R) and i < len(L)) {
            B.append([空栏 c])
            i = i + 1
        } else if ([空栏 d]) {
            B.append(L[i])
            i = i + 1
        } else {
            B.append(R[j])
            j = j + 1
        }
    }
    print(B)
    return B
}

1. 填写空栏 a、b、c、d 中的代码。
2. 执行 func([2,9,5,3,7,0,1,4]) 时，按输出先后写出所有 print 的结果。
3. 给出该排序算法的时间复杂度并说明依据。

考点

• 归并排序实现：补全合并两个有序子数组时的循环条件、剩余元素处理与比较条件。
• 递归执行跟踪：按实际递归返回顺序列出各层合并数组的输出。
• 分治复杂度：由 $T(n)=2T(n/2)+\Theta(n)$ 推出 $\Theta(n\log n)$。

Kai

(1)

• [空欄 a]: i < len(L) or j < len(R)
• [空欄 b]: R[j]
• [空欄 c]: L[i]
• [空欄 d]: L[i] < R[j]

(2)

2 9
3 5
2 3 5 9
0 7
1 4
0 1 4 7
0 1 2 3 4 5 7 9

(3)

Let $T(n)$ denote the time taken to sort $n$ elements. Then we have

$$\begin{aligned} T(n) &= \underbrace{T(n/2)} + \underbrace{T(n/2)} + \underbrace{O(n)} \\ &\quad \ \text{(sort L)} \quad \text{(sort R)} \ \text{(merge)} \\ &= 2T(n/2) + O(n) \\ &= 2^kT(\frac{n}{2^k}) + k \cdot O(n) \\ &= n T(1) + \log n \cdot O(n) \\ &= O(n \log n) \end{aligned}$$

Therefore, the time complexity is $O(n \log n)$