跳到主要内容

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

Author​

zephyr

Description​

自然数 の大きさの入力データを処理するアルゴリズムの最悪計算時間を 、実数 以下の最大の整数を と記述する。 を定数とする。 が および のとき以下の再帰的定義をみたす場合を各々考える。

  • (1)
  • (2)
  • (3)
  • (4)
  • (5)

各再帰的定義を満たす が属する最小のクラスを以下の計算量クラスから選び、その証明を示せ。

Let denote the worst-case running time of an algorithm that processes input data of size . Let be the largest integer that is equal to or smaller than real number . Let be a constant number. Suppose that meets and each of the following recurrences for :

  • (1)
  • (2)
  • (3)
  • (4)
  • (5)

From the following complexity classes, select the smallest class for that satisfies each of the above recurrences, and prove the property:

Kai​

(1)​

For this recurrence, we use the Master Theorem. The recurrence is of the form .

  • Here, , , and .
  • We need to compare with .

First, compute :

According to the Master Theorem:

  • If where , then .
  • If , then .
  • If where and for some and sufficiently large , then .

In this case, and .

Since , we have .

Thus, .

(2)​

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

When :

The sum is a geometric series:

Thus, can be approximated by:

Thus, .

(3)​

This is a non-homogeneous linear recurrence relation. We can use the iterative method:

The sum is:

And the sum is:

Therefore:

Thus, .

(4)​

For this recurrence, we again use the Master Theorem. The recurrence is of the form .

  • Here, , , and .
  • We need to compare with .

First, compute :

According to the Master Theorem:

  • If where , then .
  • If , then .
  • If where and for some and sufficiently large , then .

In this case, and .

Since is :

Thus, .

(5)​

For this recurrence, we use the Master Theorem. The recurrence is of the form .

  • Here, , , and .
  • We need to compare with .

First, compute :

According to the Master Theorem:

  • If where , then .
  • If , then .
  • If where and for some and sufficiently large , then .

In this case, and .

Since , we have:

Thus, .

Summary​

  • Recurrence 1: , .
  • Recurrence 2: , .
  • Recurrence 3: , .
  • Recurrence 4: , .
  • Recurrence 5: , .

Knowledge​

主定理 递归 复杂度分析

解题技巧和信息​

对于递归方程的时间复杂度分析，使用主定理是一个强大的工具。主定理适用于形如 的递归式。需要注意 的取值以及 和 的比较来判断最终的时间复杂度。对于不能用主定理的递归式，可以使用展开迭代法逐步分析。

重点词汇​

  • Recurrence Relation 递归关系
  • Master Theorem 主定理
  • Time Complexity 时间复杂度
  • Logarithm 对数
  • Big O Notation 大 O 符号

参考资料​

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, Chapter 4.