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

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
}

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)\)

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