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

Author

zephyr

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)\) 中。

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 we can choose any positive constant \(c_0\) and it will be less than \(2^n\) for sufficiently large \(n\). Thus, we can choose \(n_0 = 1\) and any \(c_0 > 0\):

\[ 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 \(n = \Omega(n^0)\) and \(g(n) = n\), 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, 3^rd 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, 6^th Edition. Wiley. Chapter 5: Recursion.