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

Author

zephyr

Description

Let be a positive integer. Let and denote functions that represent computation time for solving a problem of size . To provide asymptotic upper and lower bounds on , we define the following sets of functions, and , respectively:

Answer the following questions.

(1) Let . Prove whether is in , and whether is in .

(2) Let . Prove whether is in , and whether is in .

(3) Let be the largest integer that is equal to or smaller than real number . Suppose that satisfies that and for . Prove whether is in , and whether is in .

---

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

回答下列问题。

(1) 令 。证明 是否在 中，以及 是否在 中。

(2) 令 。证明 是否在 中，以及 是否在 中。

(3) 设 为等于或小于实数 的最大整数。假设 满足 且 对于 。证明 是否在 中，以及 是否在 中。

Kai

(1)

Part (a): Prove whether is in

To prove , we need to find constants and such that:

Notice that . This grows much faster than . To find such and :

For this to hold for all , would have to be infinite, which is not possible. Therefore,

Part (b): Prove whether is in

To prove , we need to find constants and such that:

Notice that:

For large , grows exponentially, so we can choose any positive constant and it will be less than for sufficiently large . Thus, we can choose and any :

(2)

Part (a): Prove whether is in

To prove , we need to find constants and such that:

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

Evaluating the integral, we get:

Thus,

For sufficiently large , the term can be bounded by for some constant . Hence,

Part (b): Prove whether is in

To prove , we need to find constants and such that:

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

Evaluating the integral, we get:

Thus,

For sufficiently large , can be bounded from below by for some constant . Thus, we can choose and :

(3)

Part (a): Prove whether is in

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

This fits the form with , , and . The Master Theorem states:

1. If where , then .
2. If , then .
3. If where , and if for some and sufficiently large , then .

In this case, , and . Since and , case 3 of the Master Theorem applies, giving us:

Thus,

Part (b): Prove whether is in

We already have from the Master Theorem that . Therefore, is not , because implies both upper and lower bounds and .

Thus,

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.