京都大学 情報学研究科 知能情報学専攻 2019年8月実施 情報学基礎 F2-1
Author
祭音Myyura
Description
以下の擬似コードで記述された関数 func(A) は数値配列 A を昇順にソートする。
A, B, L, R は数値配列であり、配列のインデックスは
(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
Therefore, the time complexity is