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

标签：

• 东京大学
• 算法复杂度
• 渐近上界与下界的证明
• 递推关系的复杂度分析

Author

zephyr, 祭音Myyura

Description

Let $n$ be a positive integer. Let $f(n)$ and $g(n)$ denote functions that represent computation time for solving a problem of size $n$. To provide asymptotic upper and lower bounds on $f(n)$, we define the following sets of functions, $O(g(n))$ and $\Omega(g(n))$, respectively:

$$O(g(n)) = \{f(n) \mid \text{There exist positive constants } c_0 \text{ and } n_0 \text{ such that } 0 \leq f(n) \leq c_0 \, g(n) \text{ for all } n \geq n_0\}$$

$$\Omega(g(n)) = \{f(n) \mid \text{There exist positive constants } c_0 \text{ and } n_0 \text{ such that } 0 \leq c_0 \, g(n) \leq f(n) \text{ for all } n \geq n_0\}$$

Answer the following questions.

(1) Let $f(n) = 2^{2n}$. Prove whether $f(n)$ is in $O(2^n)$, and whether $f(n)$ is in $\Omega(2^n)$.

(2) Let $f(n) = \sum_{i=1}^{n}(1/i)$. Prove whether $f(n)$ is in $O(\log n)$, and whether $f(n)$ is in $\Omega(\log n)$.

(3) Let $\lfloor x \rfloor$ be the largest integer that is equal to or smaller than real number $x$. Suppose that $f(n)$ satisfies that $f(1) = 1$ and $f(n) = f(\lfloor n/2 \rfloor) + n$ for $n \geq 2$. Prove whether $f(n)$ is in $O(n)$, and whether $f(n)$ is in $\Omega(n^2)$.

---

设 $n$ 为正整数。令 $f(n)$ 和 $g(n)$ 表示解决大小为 $n$ 的问题的计算时间函数。为了提供 $f(n)$ 的渐近上界和下界，我们分别定义了以下函数集 $O(g(n))$ 和 $\Omega(g(n))$：

$$O(g(n)) = \{f(n) \mid \text{存在正常数 } c_0 \text{ 和 } n_0 \text{ 使得 } 0 \leq f(n) \leq c_0 \, g(n) \text{ 对于所有 } n \geq n_0\}$$

$$\Omega(g(n)) = \{f(n) \mid \text{存在正常数 } c_0 \text{ 和 } n_0 \text{ 使得 } 0 \leq c_0 \, g(n) \leq f(n) \text{ 对于所有 } n \geq n_0\}$$

回答下列问题。

(1) 令 $f(n) = 2^{2n}$。证明 $f(n)$ 是否在 $O(2^n)$ 中，以及 $f(n)$ 是否在 $\Omega(2^n)$ 中。

(2) 令 $f(n) = \sum_{i=1}^{n}(1/i)$。证明 $f(n)$ 是否在 $O(\log n)$ 中，以及 $f(n)$ 是否在 $\Omega(\log n)$ 中。

(3) 设 $\lfloor x \rfloor$ 为等于或小于实数 $x$ 的最大整数。假设 $f(n)$ 满足 $f(1) = 1$ 且 $f(n) = f(\lfloor n/2 \rfloor) + n$ 对于 $n \geq 2$。证明 $f(n)$ 是否在 $O(n)$ 中，以及 $f(n)$ 是否在 $\Omega(n^2)$ 中。

题目描述

设 $n$ 为正整数，$f(n),g(n)$ 表示处理规模 $n$ 问题的运行时间。定义

$$O(g(n))=\{f(n)\mid \exists c_0,n_0>0,\ \forall n\ge n_0,\ 0\le f(n)\le c_0g(n)\},$$

$$\Omega(g(n))=\{f(n)\mid \exists c_0,n_0>0,\ \forall n\ge n_0,\ 0\le c_0g(n)\le f(n)\}.$$

对下列各情形，分别按定义判断所给上界或下界是否成立，并给出证明：

1. $f(n)=2^{2n}$ 时，判断 $f(n)\in O(2^n)$ 与 $f(n)\in\Omega(2^n)$。

2. $f(n)=\sum_{i=1}^{n}\frac1i$ 时，判断 $f(n)\in O(\log n)$ 与 $f(n)\in\Omega(\log n)$。

3. 令 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。若

   $$f(1)=1,\qquad f(n)=f(\lfloor n/2\rfloor)+n\quad(n\ge2),$$

   判断 $f(n)\in O(n)$ 与 $f(n)\in\Omega(n^2)$。

Kai

(1)

Part (a): Prove whether $f(n)$ is in $O(2^n)$

To prove $f(n) \in O(2^n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0 \leq 2^{2n} \leq c_0 \cdot 2^n \text{ for all } n \geq n_0.$$

Notice that $2^{2n} = (2^n)^2$. This grows much faster than $2^n$. To find such $c_0$ and $n_0$:

$$2^{2n} \leq c_0 \cdot 2^n \Rightarrow 2^n \leq c_0.$$

For this to hold for all $n \geq n_0$, $c_0$ would have to be infinite, which is not possible. Therefore,

$$f(n) = 2^{2n} \notin O(2^n).$$

Part (b): Prove whether $f(n)$ is in $\Omega(2^n)$

To prove $f(n) \in \Omega(2^n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0 \leq c_0 \cdot 2^n \leq 2^{2n} \text{ for all } n \geq n_0.$$

Notice that:

$$c_0 \cdot 2^n \leq 2^{2n} \Rightarrow c_0 \leq 2^n.$$

For large $n$, $2^n$ grows exponentially, so any fixed positive $c_0$ will be less than $2^n$ for sufficiently large $n$. For example, choose $c_0=1$ and $n_0=1$:

$$f(n) = 2^{2n} \in \Omega(2^n).$$

(2)

Part (a): Prove whether $f(n)$ is in $O(\log n)$

To prove $f(n) \in O(\log n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0 \leq \sum_{i=1}^n \frac{1}{i} \leq c_0 \log n \text{ for all } n \geq n_0.$$

Let's use the properties of the harmonic series. We know that:

$$\sum_{i=1}^{n} \frac{1}{i} \leq 1 + \int_{1}^{n} \frac{1}{x} \, \mathrm{d}x.$$

Evaluating the integral, we get:

$$\int_{1}^{n} \frac{1}{x} \, \mathrm{d}x = \log n.$$

Thus,

$$\sum_{i=1}^{n} \frac{1}{i} \leq 1 + \log n.$$

For sufficiently large $n$, the term $1 + \log n$ can be bounded by $c_0 \log n$ for some constant $c_0 \geq 1$. Hence,

$$f(n) = \sum_{i=1}^n \frac{1}{i} \in O(\log n).$$

Part (b): Prove whether $f(n)$ is in $\Omega(\log n)$

To prove $f(n) \in \Omega(\log n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0 \leq c_0 \log n \leq \sum_{i=1}^n \frac{1}{i} \text{ for all } n \geq n_0.$$

We can compare the harmonic series with the integral from below. Specifically,

$$\sum_{i=1}^{n} \frac{1}{i} \geq \int_{1}^{n+1} \frac{1}{x} \, \mathrm{d}x.$$

Evaluating the integral, we get:

$$\int_{1}^{n+1} \frac{1}{x} \, \mathrm{d}x = \log (n+1).$$

Thus,

$$\sum_{i=1}^{n} \frac{1}{i} \geq \log (n+1).$$

For sufficiently large $n$, $\log (n+1)$ can be bounded from below by $c_0 \log n$ for some constant $c_0 > 0$. Thus, we can choose $c_0 = 1$ and $n_0 = 1$:

$$f(n) = \sum_{i=1}^n \frac{1}{i} \in \Omega(\log n).$$

(3)

Part (a): Prove whether $f(n)$ is in $O(n)$

To analyze this, we use the Master Theorem for divide-and-conquer recurrences. Here, the recurrence is:

$$f(n) = f(\lfloor n/2 \rfloor) + n.$$

This fits the form $f(n) = a f(n/b) + g(n)$ with $a = 1$, $b = 2$, and $g(n) = n$. The Master Theorem states:

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

In this case, $\log_b a = \log_2 1 = 0$, and $g(n) = n$. Since $g(n)=\Theta(n)$ has exponent $1>0$ and $g(n/2)=g(n)/2$, case 3 of the Master Theorem applies, giving us:

$$f(n) = \Theta(n).$$

Thus,

$$f(n) \in O(n).$$

Part (b): Prove whether $f(n)$ is in $\Omega(n^2)$

We already have from the Master Theorem that $f(n) = \Theta(n)$. Therefore, $f(n)$ is not $\Omega(n^2)$, because $\Theta(n)$ implies both upper and lower bounds $O(n)$ and $\Omega(n)$.

Thus,

$$f(n) \notin \Omega(n^2).$$

Knowledge

递归 主定理 复杂度分析

重点词汇

• Asymptotic bounds 渐近界
• Master Theorem 主定理
• Harmonic series 调和级数
• Exponential function 指数函数
• Recurrence 递归

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press. Chapter 3: Growth of Functions, and Chapter 4: Divide-and-Conquer.
2. Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser. Data Structures and Algorithms in Java, 6th Edition. Wiley. Chapter 5: Recursion.

Reference

• 東京大学 CBMS 公式過去問