東京大学 新領域創成科学研究科 メディカル情報生命専攻 2024年1月実施 問題7

Author

水月, 祭音Myyura

Description

入力データサイズ \(n\) に対して計算時間 \(T(n)\) を考える。 以下の再帰方程式 (1)～(3) それぞれについて \(T(n)\) の計算量を \(n\) の式で表せ。 必要に応じて \(O()\) などのランダウ記法を用いてもよい。 ただし、\(T(0) = 1\) とし、\(\lfloor x \rfloor\) は \(x\) を超えない最大の整数を表す。

(1) \(T(n) = T(n-1) + 2n\)

(2) \(T(n) = T(\lfloor n/3 \rfloor) + 1\)

(3) \(T(n) = 2T(\lfloor n/2 \rfloor) + n + 1\)

以下の (4) の命題は成り立つか？最初に真偽を述べ、それが正しいことを証明せよ。

(4) \(T(n) \in O(2^n)\) と \(T(n) \in O(e^n)\) は同値である。

以下の (5) の再帰方程式が成り立つとき、\(T(n)\) の計算量を \(n\) の式で表せ。ただし、\(a\) は正の定数である。

(5) \(T(n) = aT(\lfloor n/2 \rfloor) + \lfloor n \log_2 n \rfloor\)

Kai

(1)

\[ \begin{aligned} T(n) &= T(n-1) + 2n \\ &=2n + 2(n-1) + 2(n-2) + \cdots + 2 \\ &= O(n^2) \end{aligned} \]

(2)

\[ \begin{aligned} T(n) &= T(\lfloor n/3 \rfloor) + 1 = O(\log n) \end{aligned} \]

(3)

Note that

\[ \frac{T(n)}{n} = \frac{T(\lfloor n/2 \rfloor)}{n/2} + 1 + \frac{1}{n} \]

hence

\[ \frac{T(2^k)}{2^k} = T(1) + k + O(1) \]

\[ \therefore T(2^k) \in \Theta(k2^k) \]

that is

\[ T(n) \in O(n \log n) \]

(4)

The statement is False.

Counter example: \(T(n) = 2.5^n\).

(5)

See Generic form of Master Theorem

\[ \begin{aligned} &T(n) = O(n \log_2 n) &\text{if } a < 2 \\ &T(n) = O(n \log_2^2 n) &\text{if } a = 2 \\ &T(n) = O(n^{\log_2 a}) &\text{if } a > 2 \end{aligned} \]