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

Author

Isidore, 祭音Myyura

Description

設問1

Kai

設問1

(1)

a. \(|L| = k\)

b. \(|L| > k\)

c. \(k\)

d. \(|L| < k\)

e. \(k - |L|\)

(2)

Note that Algorithm 1 is so called "Quick Select" algorithm. Let \(T(n)\) denote the expected time complexity of Quick-Select, we have

\[ \begin{aligned} T(n) &= O(n) + T(\frac{n}{2}) \\ &= O(n) + O(\frac{n}{2}) + T(\frac{n}{4}) \\ &= O(n) + O(\frac{n}{2}) + O(\frac{n}{4}) + \cdots + O(1) \\ &\sim n (1 + \frac{1}{2} + \frac{1}{4} + \cdots + \left(\frac{1}{2} \right)^{\log n}) \\ &= n \cdot \frac{1}{1-\frac{1}{2}} = 2n \end{aligned} \]

Therefore, \(T(n) = O(n)\)

設問2

(1)

index	list
0	2101 -> 1111
1	0100 -> 1211 -> 0010
2
3	1222

(2)

• (a): 0
• (b): 2
• (\(c\)): 3
• (d): 1

Reason: to minimize the cost is to equalize the probability to insert each list

(3)

Construct a system of six linear equations in six variables from the table given in (2), and we have

\[ \begin{aligned} a_1 &= 1 \\ a_2 &= 2 \\ a_3 &= 0 \\ a_4 &= -2 \\ a_5 &= 0 \\ a_6 &= 2 \\ \end{aligned} \]