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

标签：

• 东京大学
• 递推关系
• 主定理
• 递推关系的复杂度分析
• 大 O 等价关系与运算规则

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$

题目描述

设 $T(n)$ 为输入规模 $n$ 对应的运行时间，规定 $T(0)=1$，且 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。可按需使用大 $O$ 等 Landau 记号。

1. 分别求下列递推的 $T(n)$ 复杂度：

   $$\begin{aligned} \text{(1)}\quad&T(n)=T(n-1)+2n,\\ \text{(2)}\quad&T(n)=T(\lfloor n/3\rfloor)+1,\\ \text{(3)}\quad&T(n)=2T(\lfloor n/2\rfloor)+n+1. \end{aligned}$$

2. 先判断下列命题真伪，再证明：

   $$T(n)\in O(2^n)\quad\Longleftrightarrow\quad T(n)\in O(e^n).$$

3. 对正常数 $a$，求递推

   $$T(n)=aT(\lfloor n/2\rfloor)+\lfloor n\log_2n\rfloor$$

   的复杂度；应根据 $a$ 与分治临界值的关系处理必要的不同情形。

Kai

Written by 水月.

(1)

$$\begin{aligned} T(n) &= T(n-1) + 2n \\ &=1 + 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 \Theta(n \log n)$$

For arbitrary $n$, the recurrence implies that $T(n)$ is nondecreasing. Bounding $n$ between consecutive powers of two extends the same asymptotic bound to all integers.

(4)

The statement is False.

Counter example: $T(n)=2.5^n$. Since $2<2.5<e$, we have $(2.5/e)^n\to0$ but $(2.5/2)^n\to\infty$. Thus this function belongs to $O(e^n)$ and does not belong to $O(2^n)$.

(5)

See Generic form of Master Theorem

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

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) = \Theta(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$.

Here $n^{\log_3 1}=1$ and $f(n)=\Theta(1)$, so case 2 of the Master Theorem gives $T(n)=\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$

At level $\ell$, the total nonrecursive cost is $n\log(n/2^\ell)$. Hence, for $n$ a power of two,

$$T(n)=nT(1)+n\sum_{\ell=0}^{\log_2n-1}(\log_2n-\ell) =\Theta(n\log^2 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 > 2$: $T(n) = \Theta(n^{\log_2 a})$

Knowledge

难点思路

第 4 小题的证明和第 5 小题的复杂度分析较为困难。对于第 4 小题，关键是理解指数函数的性质和大 O 符号的定义。对于第 5 小题，由于不能直接应用主定理，需要通过猜测和归纳证明的方法来解决。

解题技巧和信息

1. 对于简单的递归方程，可以尝试使用迭代法直接求解。
2. 对于符合形式的递归方程，优先考虑使用主定理。
3. 当递归方程不能直接应用主定理时，可以尝试猜测复杂度并使用归纳法证明。
4. 在处理渐进符号时，要注意指数函数、对数函数等的性质。

常见算法复杂度排序（从低到高）：

$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 下取整函数

参考资料

1. Introduction to Algorithms (CLRS), Chapter 4: Divide-and-Conquer
2. Algorithm Design (Kleinberg & Tardos), Chapter 5: Divide and Conquer
3. The Art of Computer Programming (Knuth), Volume 1: Fundamental Algorithms, Section 1.2.11: Asymptotic Representations