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

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, 3^rd Edition. MIT Press, Chapter 4.