広島大学 先進理工系科学研究科 情報科学プログラム 2021年8月実施 専門科目II 問題2
Author
祭音Myyura
Description
集合の中で Select(A, p, r, i)
に示す。
Select(A, p, r, i)
は配列
(1) 配列 Select(A, 1, 10, 3)
が返す値を書け。
(2) (1) の配列 Select(A, 1, 10, 3)
を呼び出すと、Select
が再帰的に呼び出される。
最初の呼び出しを含めて、Select
の呼出しごとのパラメーター
(3) 空欄
(4) 昇順に整列された Select(A, 1, n, 1)
が呼び出されたとき、Partition
の 4 行目の比較が行われる回数を数えよ。
(5) Select
の期待計算時間をビッグオー記法で示し、その理由を簡潔に説明せよ。
Select(A, p, r, i)
is an algorithm to find the Select(A, p, r, i)
returns the
(1) For array Select(A, 1, 10, 3)
.
(2) When we call Select(A, 1, 10, 3)
for array Select
is called recursively
Describe the values of parameters Select
, including the first call. All elements of array
(3) Fill blanks
(4) Count the number of comparisons on the 4th line of Partition
, when Select(A, 1, n, 1)
is called with sorted array
(5) Show the expected time complexity of Select
for a set of

Kai
(1)
(2)
(3)
- blank
: - blank
: - blank
:
(4)
When array Partition(A, p, r)
will always return
Hence the number of comparisions on the 4th line of Partition
is
(5)
Let Select
for a set of