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

标签：

• Tokyo-University
• Recurrence-Relation-Complexity
• Master-Theorem

Author

zephyr

Description

自然数 $n (\geq 1)$ の大きさの入力データを処理するアルゴリズムの最悪計算時間を $T(n)$、実数 $x$ 以下の最大の整数を $\lfloor x \rfloor$ と記述する。 $c \geq 1$ を定数とする。 $T(n)$ が $T(1)=c$ および $n>1$ のとき以下の再帰的定義をみたす場合を各々考える。

• (1) $T(n) = T(\lfloor 3n/4 \rfloor) + cn$
• (2) $T(n) = 2T(n - 1) + cn$
• (3) $T(n) = T(n - 1) + c(n^2 + n)$
• (4) $T(n) = T(\lfloor n/2 \rfloor) + c$
• (5) $T(n) = 2T(\lfloor n/2 \rfloor) + cn$

各再帰的定義を満たす $T(n)$ が属する最小のクラスを以下の計算量クラスから選び、その証明を示せ。

$$O(1), O(\log n), O(n), O(n \log n), O(n^2), O(n^3), O(3^n)$$

---

Let $T(n)$ denote the worst-case running time of an algorithm that processes input data of size $n (\geq 1)$. Let $\lfloor x \rfloor$ be the largest integer that is equal to or smaller than real number $x$. Let $c (\geq 1)$ be a constant number. Suppose that $T(n)$ meets $T(1) = c$ and each of the following recurrences for $n > 1$:

• (1) $T(n) = T(\lfloor 3n/4 \rfloor) + cn$
• (2) $T(n) = 2T(n - 1) + cn$
• (3) $T(n) = T(n - 1) + c(n^2 + n)$
• (4) $T(n) = T(\lfloor n/2 \rfloor) + c$
• (5) $T(n) = 2T(\lfloor n/2 \rfloor) + cn$

From the following complexity classes, select the smallest class for $T(n)$ that satisfies each of the above recurrences, and prove the property:

$$O(1), O(\log n), O(n), O(n \log n), O(n^2), O(n^3), O(3^n)$$

Kai

(1)

For this recurrence, we use the Master Theorem. The recurrence is of the form $T(n) = aT(n/b) + f(n)$.

• Here, $a = 1$, $b = \frac{4}{3}$, and $f(n) = cn$.
• We need to compare $f(n)$ with $n^{\log_b a}$.

First, compute $\log_b a$:

$$\log_b a = \log_{4/3} 1 = 0$$

According to the Master Theorem:

• If $f(n) = O(n^c)$ where $c < \log_b a$, then $T(n) = \Theta(n^{\log_b a})$.
• If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
• If $f(n) = \Omega(n^c)$ where $c > \log_b a$ and $af(n/b) \leq kf(n)$ for some $k < 1$ and sufficiently large $n$, then $T(n) = \Theta(f(n))$.

In this case, $f(n) = cn = \Theta(n)$ and $\log_b a = 0$.

Since $c > \log_b a$, we have $T(n) = \Theta(n)$.

Thus, $T(n) \in O(n)$.

(2)

To solve this recurrence, we can use the iterative method:

$$\begin{aligned} T(n) & = 2T(n - 1) + cn \\ & = 2[2T(n - 2) + c(n - 1)] + cn \\ & = 2^2T(n - 2) + 2c(n - 1) + cn \\ & = 2^2[2T(n - 3) + c(n - 2)] + 2c(n - 1) + cn \\ & = 2^3T(n - 3) + 2^2c(n - 2) + 2c(n - 1) + cn \\ &\qquad \qquad \qquad \vdots \\ & = 2^kT(n - k) + c\sum_{i=0}^{k-1} 2^i(n - i) \end{aligned}$$

When $k = n - 1$:

$$\begin{aligned} T(n) & = 2^{n-1}T(1) + c\sum_{i=0}^{n-2} 2^i(n - i) \\ & = 2^{n-1}c + c\sum_{i=0}^{n-2} 2^i(n - i) \\ & = 2^{n-1}c + c\left( \sum_{i=1}^{n-1} 2^i (n - i + 1) - \sum_{i=0}^{n-2} 2^i(n - i) \right) \\ & = 2^{n-1}c + c\left( 2^n + \sum_{i=1}^{n-2} 2^i (n - i + 1) - \sum_{i=1}^{n-2} 2^i(n - i) - n \right) \\ & = 2^{n-1}c + c\left( 2^n - n + \sum_{i=1}^{n-2} 2^i \right) \\ \end{aligned}$$

The sum $\sum_{i=1}^{n-2} 2^i$ is a geometric series:

$$\sum_{i=1}^{n-2} 2^i = 2^{n-1} - 2$$

Thus, $T(n)$ can be approximated by:

$$T(n) = \Theta(2^n) = O(3^n)$$

Thus, $T(n) \in O(3^n)$.

(3)

This is a non-homogeneous linear recurrence relation. We can use the iterative method:

$$\begin{aligned} T(n) & = T(n-1) + c(n^2 + n) \\ & = T(n-2) + c((n-1)^2 + (n-1)) + c(n^2 + n) \\ & = T(n-3) + c((n-2)^2 + (n-2)) + c((n-1)^2 + (n-1)) + c(n^2 + n) \\ &\qquad \qquad \quad \vdots \\ & = T(1) + c \sum_{k=1}^{n-1} (k^2 + k) \\ & = c + c \sum_{k=1}^{n-1} (k^2 + k) \end{aligned}$$

The sum $\sum_{k=1}^{n-1} k^2$ is:

$$\sum_{k=1}^{n-1} k^2 = \frac{(n-1)n(2n-1)}{6}$$

And the sum $\sum_{k=1}^{n-1} k$ is:

$$\sum_{k=1}^{n-1} k = \frac{(n-1)n}{2}$$

Therefore:

$$\begin{aligned} T(n) & = c + c \left( \frac{(n-1)n(2n-1)}{6} + \frac{(n-1)n}{2} \right) \\ & = c + c \left( \frac{(n-1)n(2n-1 + 3)}{6} \right) \\ & = c + c \left( \frac{(n-1)n(2n+2)}{6} \right) \\ & = c + \frac{c(n-1)n(n+1)}{3} \\ & = \Theta(n^3) \end{aligned}$$

Thus, $T(n) \in O(n^3)$.

(4)

For this recurrence, we again use the Master Theorem. The recurrence is of the form $T(n) = aT(n/b) + f(n)$.

• Here, $a = 1$, $b = 2$, and $f(n) = c$.
• We need to compare $f(n)$ with $n^{\log_b a}$.

First, compute $\log_b a$:

$$\log_b a = \log_2 1 = 0$$

According to the Master Theorem:

• If $f(n) = O(n^c)$ where $c < \log_b a$, then $T(n) = \Theta(n^{\log_b a})$.
• If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
• If $f(n) = \Omega(n^c)$ where $c > \log_b a$ and $af(n/b) \leq kf(n)$ for some $k < 1$ and sufficiently large $n$, then $T(n) = \Theta(f(n))$.

In this case, $f(n) = c = \Theta(1)$ and $\log_b a = 0$.

Since $f(n)$ is $\Theta(n^0)$:

$$T(n) = \Theta(\log n)$$

Thus, $T(n) \in O(\log n)$.

(5)

For this recurrence, we use the Master Theorem. The recurrence is of the form $T(n) = aT(n/b) + f(n)$.

• Here, $a = 2$, $b = 2$, and $f(n) = cn$.
• We need to compare $f(n)$ with $n^{\log_b a}$.

First, compute $\log_b a$:

$$\log_b a = \log_2 2 = 1$$

According to the Master Theorem:

• If $f(n) = O(n^c)$ where $c < \log_b a$, then $T(n) = \Theta(n^{\log_b a})$.
• If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
• If $f(n) = \Omega(n^c)$ where $c > \log_b a$ and $af(n/b) \leq kf(n)$ for some $k < 1$ and sufficiently large $n$, then $T(n) = \Theta(f(n))$.

In this case, $f(n) = cn = \Theta(n)$ and $\log_b a = 1$.

Since $f(n) = \Theta(n^{\log_b a})$, we have:

$$T(n) = \Theta(n \log n)$$

Thus, $T(n) \in O(n \log n)$.

Summary

• Recurrence 1: $T(n) = \Theta(n)$, $T(n) \in O(n)$.
• Recurrence 2: $T(n) = \Theta(2^n)$, $T(n) \in O(2^n)$.
• Recurrence 3: $T(n) = \Theta(n^3)$, $T(n) \in O(n^3)$.
• Recurrence 4: $T(n) = \Theta(\log n)$, $T(n) \in O(\log n)$.
• Recurrence 5: $T(n) = \Theta(n \log n)$, $T(n) \in O(n \log n)$.

Knowledge

主定理 递归 复杂度分析

解题技巧和信息

对于递归方程的时间复杂度分析，使用主定理是一个强大的工具。主定理适用于形如 $T(n) = aT(n/b) + f(n)$ 的递归式。需要注意 $a, b, f(n)$ 的取值以及 $f(n)$ 和 $n^{\log_b a}$ 的比较来判断最终的时间复杂度。对于不能用主定理的递归式，可以使用展开迭代法逐步分析。

重点词汇

• Recurrence Relation 递归关系
• Master Theorem 主定理
• Time Complexity 时间复杂度
• Logarithm 对数
• Big O Notation 大 O 符号

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, Chapter 4.