東京大学 新領域創成科学研究科 メディカル情報生命専攻 2024年1月実施 問題7
Author
水月, 祭音Myyura, zephyr
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\)
Let \(T(n)\) be the computation time in terms of the input size \(n\). For each of the recurrences (1)-(3) shown below, write the complexity of \(T(n)\) in terms of \(n\). You may use Landau notations such as \(O()\) if need be. Assume that \(T(0) = 1\). Note that \(\lfloor x \rfloor\) is the maximum integer that is not larger than \(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\)
Does the following proposition (4) hold true? State true or false first and prove it.
(4) \(T(n) \in O(2^n)\) if and only if \(T(n) \in O(e^n)\).
Given the following recurrence (5), write the complexity of \(T(n)\) in terms of \(n\). \(a\) is a positive constant.
(5) \(T(n) = aT(\lfloor n/2 \rfloor) + \lfloor n \log_2 n \rfloor\)
设 \(T(n)\) 为输入大小 \(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
Written by 水月.
(1)
(2)
(3)
Note that
hence
that is
(4)
The statement is False.
Counter example: \(T(n) = 2.5^n\).
(5)
See Generic form of Master Theorem
Kai
Written by zephyr.
解题思路
这道题目主要涉及递归方程的复杂度分析和渐进符号的性质。我们需要运用主定理、迭代法等技巧来解决递归方程，并理解大 O 符号的性质来证明命题。对于最后一个问题，我们需要根据递归方程的形式来判断使用哪种方法求解。
1. \(T(n) = T(n - 1) + 2n\)
To solve this recurrence, we can use the iteration method:
\(T(n) = T(n-1) + 2n\)
\(= [T(n-2) + 2(n-1)] + 2n\)
\(= [T(n-3) + 2(n-2)] + 2(n-1) + 2n\)
\(= \cdots\)
\(= T(0) + 2[1 + 2 + \cdots + (n-1) + n]\)
\(= 1 + 2[\frac{n(n+1)}{2}]\)
\(= 1 + n(n+1)\)
\(= n^2 + n + 1\)
Therefore, \(T(n) = O(n^2)\).
2. \(T(n) = T(\lfloor n/3 \rfloor) + 1\)
This recurrence fits the form of the Master Theorem with \(a=1\), \(b=3\), and \(f(n) = 1\).
Since \(f(n) = O(n^{\log_3 1 - \epsilon})\) for \(\epsilon > 0\), we are in case 1 of the Master Theorem.
Therefore, \(T(n) = \Theta(n^{\log_3 1}) = \Theta(\log n)\).
3. \(T(n) = 2T(\lfloor n/2 \rfloor) + n + 1\)
This recurrence also fits the form of the Master Theorem with \(a=2\), \(b=2\), and \(f(n) = n + 1\).
Since \(f(n) = \Theta(n^{\log_2 2}) = \Theta(n)\), we are in case 2 of the Master Theorem.
Therefore, \(T(n) = \Theta(n \log n)\).
4. \(T(n) \in O(2^n)\) if and only if \(T(n) \in O(e^n)\)
This proposition is false. Let's examine both directions:
Part 1: If \(T(n) \in O(2^n)\), then \(T(n) \in O(e^n)\)
This direction is true.
Proof: Assume \(T(n) \in O(2^n)\). By definition, \(\exists c > 0\) and \(n_0 > 0\) such that \(T(n) \leq c2^n\) for all \(n \geq n_0\).
We know that \(2^n = (e^{\ln 2})^n = e^{n\ln 2}\).
Since \(\ln 2 < 1\), we have \(e^{n\ln 2} < e^n\) for all \(n > 0\).
Therefore, \(T(n) \leq c2^n = ce^{n\ln 2} < ce^n\) for all \(n \geq n_0\).
This means \(T(n) \in O(e^n)\).
Part 2: If \(T(n) \in O(e^n)\), then \(T(n) \in O(2^n)\)
This direction is false.
Consider the function \(T(n) = e^n \in O(e^n)\).
\(\lim_{n \to \infty} \frac{e^n}{2^n} = \lim_{n \to \infty} (\frac{e}{2})^n = \infty\)
This means that for any constant \(c\), there will always be some \(n\) where \(e^n > c2^n\).
Therefore, the statement "if \(T(n) \in O(e^n)\), then \(T(n) \in O(2^n)\)" is false.
Conclusion
The original proposition is false because while \(O(2^n) \subset O(e^n)\), the reverse inclusion does not hold. There are functions in \(O(e^n)\) that grow faster than any function in \(O(2^n)\).
A correct statement would be: If \(T(n) \in O(2^n)\), then \(T(n) \in O(e^n)\), but the converse is not necessarily true.
5. \(T(n) = aT(\lfloor n/2 \rfloor) + \lfloor n \log_2 n \rfloor\)
Let's analyze this recurrence for different cases of \(a\). We'll ignore the floor functions for the asymptotic analysis as they don't affect the overall complexity.
Case 1: \(a < 2\)
In this case, we can use a variant of the Master Theorem. We have:
\(T(n) = aT(n/2) + n\log n\)
Here, \(f(n) = n\log n\). We need to compare \(n^{\log_2 a}\) with \(f(n) = n\log n\).
Since \(a < 2\), we have \(n^{\log_2 a} < n\). Therefore, \(f(n) = n\log n\) is asymptotically larger.
Thus, \(T(n) = \Theta(n\log n)\) when \(a < 2\).
Case 2: \(a = 2\)
When \(a = 2\), we have:
\(T(n) = 2T(n/2) + n\log n\)
This case doesn't fit directly into the Master Theorem. Let's solve it by substitution:
\(T(n) = 2T(n/2) + n\log n\) \(= 2[2T(n/4) + (n/2)\log(n/2)] + n\log n\) \(= 4T(n/4) + n\log(n/2) + n\log n\) \(= 4T(n/4) + n\log n + n\log n - n\) \(= 4T(n/4) + 2n\log n - n\)
Continuing this process, we get:
\(T(n) = nT(1) + n\log n \sum_{i=1}^{\log n} 2 - n\sum_{i=1}^{\log n} 1\) \(= nT(1) + 2n\log^2 n - n\log n\)
Therefore, when \(a = 2\), \(T(n) = \Theta(n\log^2 n)\).
Case 3: \(2 < a < 4\)
In this case, we again compare \(n^{\log_2 a}\) with \(n\log n\).
Since \(2 < a < 4\), we have \(1 < \log_2 a < 2\).
This means \(n < n^{\log_2 a} < n^2\), but \(n\log n\) is asymptotically smaller than \(n^{\log_2 a}\).
Therefore, when \(2 < a < 4\), \(T(n) = \Theta(n^{\log_2 a})\).
Case 4: \(a \geq 4\)
When \(a \geq 4\), we have \(\log_2 a \geq 2\).
In this case, \(n^{\log_2 a} \geq n^2\), which is asymptotically larger than \(n\log n\).
Therefore, when \(a \geq 4\), \(T(n) = \Theta(n^{\log_2 a})\).
Summary
- For \(0 < a < 2\): \(T(n) = \Theta(n\log n)\)
- For \(a = 2\): \(T(n) = \Theta(n\log^2 n)\)
- For \(a \geq 2\): \(T(n) = \Theta(n^{\log_2 a})\)
Knowledge
难点思路
第 4 小题的证明和第 5 小题的复杂度分析较为困难。对于第 4 小题，关键是理解指数函数的性质和大 O 符号的定义。对于第 5 小题，由于不能直接应用主定理，需要通过猜测和归纳证明的方法来解决。
解题技巧和信息
- 对于简单的递归方程，可以尝试使用迭代法直接求解。
- 对于符合形式的递归方程，优先考虑使用主定理。
- 当递归方程不能直接应用主定理时，可以尝试猜测复杂度并使用归纳法证明。
- 在处理渐进符号时，要注意指数函数、对数函数等的性质。
常见算法复杂度排序（从低到高）：
\(O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)\)
重点词汇
- recurrence relation 递归关系
- Master Theorem 主定理
- iteration method 迭代法
- induction proof 归纳证明
- asymptotic notation 渐进符号
- floor function 下取整函数
参考资料
- Introduction to Algorithms (CLRS), Chapter 4: Divide-and-Conquer
- Algorithm Design (Kleinberg & Tardos), Chapter 5: Divide and Conquer
- The Art of Computer Programming (Knuth), Volume 1: Fundamental Algorithms, Section 1.2.11: Asymptotic Representations