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

Author

水月, 祭音Myyura, zephyr

Description

入力データサイズ に対して計算時間 を考える。 以下の再帰方程式 (1)～(3) それぞれについて の計算量を の式で表せ。 必要に応じて などのランダウ記法を用いてもよい。 ただし、 とし、 は を超えない最大の整数を表す。

(1)

(2)

(3)

以下の (4) の命題は成り立つか？最初に真偽を述べ、それが正しいことを証明せよ。

(4) と は同値である。

以下の (5) の再帰方程式が成り立つとき、 の計算量を の式で表せ。ただし、 は正の定数である。

(5)

---

Let be the computation time in terms of the input size . For each of the recurrences (1)-(3) shown below, write the complexity of in terms of . You may use Landau notations such as if need be. Assume that . Note that is the maximum integer that is not larger than .

(1) (2) (3)

Does the following proposition (4) hold true? State true or false first and prove it.

(4) if and only if .

Given the following recurrence (5), write the complexity of in terms of . is a positive constant.

(5)

---

设 为输入大小 的计算时间。对于下列递推关系（1）-（3），写出 关于 的复杂度。若有必要，可以使用朗道符号如 。假设 。注意， 是小于等于 的最大整数。

(1) (2) (3)

以下命题（4）是否成立？首先陈述真伪并证明。

(4) 当且仅当 。

给定下列递推关系（5），写出 关于 的复杂度。 是一个正常数。

(5)

Kai

Written by 水月.

(1)

(2)

(3)

Note that

hence

that is

(4)

The statement is False.

Counter example: .

(5)

See Generic form of Master Theorem

Kai

Written by zephyr.

解题思路

这道题目主要涉及递归方程的复杂度分析和渐进符号的性质。我们需要运用主定理、迭代法等技巧来解决递归方程，并理解大 O 符号的性质来证明命题。对于最后一个问题，我们需要根据递归方程的形式来判断使用哪种方法求解。

1.

To solve this recurrence, we can use the iteration method:

Therefore, .

2.

This recurrence fits the form of the Master Theorem with , , and .

Since for , we are in case 1 of the Master Theorem.

Therefore, .

3.

This recurrence also fits the form of the Master Theorem with , , and .

Since , we are in case 2 of the Master Theorem.

Therefore, .

4. if and only if

This proposition is false. Let's examine both directions:

Part 1: If , then

This direction is true.

Proof: Assume . By definition, and such that for all .

We know that .

Since , we have for all .

Therefore, for all .

This means .

Part 2: If , then

This direction is false.

Consider the function .

This means that for any constant , there will always be some where .

Therefore, the statement "if , then " is false.

Conclusion

The original proposition is false because while , the reverse inclusion does not hold. There are functions in that grow faster than any function in .

A correct statement would be: If , then , but the converse is not necessarily true.

5.

Let's analyze this recurrence for different cases of . We'll ignore the floor functions for the asymptotic analysis as they don't affect the overall complexity.

Case 1:

In this case, we can use a variant of the Master Theorem. We have:

Here, . We need to compare with .

Since , we have . Therefore, is asymptotically larger.

Thus, when .

Case 2:

When , we have:

This case doesn't fit directly into the Master Theorem. Let's solve it by substitution:

Continuing this process, we get:

Therefore, when , .

Case 3:

In this case, we again compare with .

Since , we have .

This means , but is asymptotically smaller than .

Therefore, when , .

Case 4:

When , we have .

In this case, , which is asymptotically larger than .

Therefore, when , .

Summary

• For :
• For :
• For :

Knowledge

难点思路

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

解题技巧和信息

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

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

重点词汇

• 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