広島大学 先進理工系科学研究科 情報科学プログラム 2018年1月実施 専門科目I 問題6
Author
祭音Myyura
Description
Algorithm 1 は、整数列
(1) 入力列
(2) Algorithm 1 の比較回数が最も多くなるような要素数が
(3) Algorithm 1 の最悪時間計算量を答えよ。また、その理由も説明せよ。
Algorithm 1 sorts an integer list
(1) Apply Algorithm 1 to the input list
(2) Show an input list such that its size is
(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
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
by master-theorem we have