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

标签：

• Tokyo-University
• Algorithm-Complexity
• Big-O-Equivalence-and-Algebra

Author

zephyr

Description

When we analyze the worst time complexity of an algorithm, it is worth observing how the computation time $T(n)$ increases as $n$ $(1 < n)$, the size of input data, increases. The Landau’s $O$ notation, which is often used for representing an asymptotic upper bound of $T(n)$ ignoring the constant factor, is defined as the following. For a positive function $f(n)$, if there exists a positive constant $c$, and

$$\lim_{{n \to \infty}} \frac{T(n)}{f(n)} < c$$

holds, then

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

is defined to hold.

(1) $O(f(n))$ and $O(g(n))$ are defined to be equal if $T(n) \in O(f(n))$ and $T(n) \in O(g(n))$ are equivalent for any $T(n)$. For each of (A) to (C), find all formulae in the box below that are equal to it. If there is no such formula, just write "none".

• (A) $O(n^3)$
• (B) $O(n \log n)$
• (C) $O(n!)$

$$\begin{array}{cccc} O(1), & O(n + 1), & O(n^2 + n + 1), & O(n^3 + n^2 + n + 1), \\ O(n^4 + n^3), & O(\log n), & O(\log_e n^2), & O((\log_e n)^n), \\ O(2n \log_2 n), & O(e^n), & O \left( \left( \frac{n}{e} \right)^n \right), & O(2^n), \\ O(n^n) \end{array}$$

(2) For each proposition below, determine with proof whether it holds or not. Note that $f(n)$ and $g(n)$ are positive functions.

• (A) $O(f(n) + g(n))$ and $O(\max(f(n), g(n)))$ are equal.
• (B) If $f(n) \in O(g(n))$ holds, then $e^{f(n)} \in O(e^{g(n)})$.

---

当我们分析一个算法的最坏时间复杂度时，观察计算时间 $T(n)$ 随输入数据大小 $n$ $(1 < n)$ 的增加而增加是很有价值的。Landau 的 $O$ 表示法，通常用于表示忽略常数因子的 $T(n)$ 的渐近上界，定义如下。对于一个正函数 $f(n)$，如果存在一个正常数 $c$，且

$$\lim_{{n \to \infty}} \frac{T(n)}{f(n)} < c$$

成立，则定义

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

成立。

(1) 如果 $T(n) \in O(f(n))$ 和 $T(n) \in O(g(n))$ 对任何 $T(n)$ 都等价，则定义 $O(f(n))$ 和 $O(g(n))$ 是相等的。对于 (A) 到 (C) 的每一个，找到下面框中等于它的所有公式。如果没有这样的公式，只写“none”。

• (A) $O(n^3)$
• (B) $O(n \log n)$
• (C) $O(n!)$

$$\begin{array}{cccc} O(1), & O(n + 1), & O(n^2 + n + 1), & O(n^3 + n^2 + n + 1), \\ O(n^4 + n^3), & O(\log n), & O(\log_e n^2), & O((\log_e n)^n), \\ O(2n \log_2 n), & O(e^n), & O \left( \left( \frac{n}{e} \right)^n \right), & O(2^n), \\ O(n^n) \end{array}$$

(2) 对于下面的每个命题，确定是否成立，并提供证明。注意 $f(n)$ 和 $g(n)$ 是正函数。

• (A) $O(f(n) + g(n))$ 和 $O(\max(f(n), g(n)))$ 是相等的。
• (B) 如果 $f(n) \in O(g(n))$ 成立，则 $e^{f(n)} \in O(e^{g(n)})$。

题目描述

设输入规模为 $n>1$，算法最坏运行时间为 $T(n)$。对正函数 $f(n)$，若存在正常数 $c$ 使

$$\lim_{n\to\infty}\frac{T(n)}{f(n)}<c,$$

则记作 $T(n)\in O(f(n))$。若对任意 $T(n)$，命题 $T(n)\in O(f(n))$ 与 $T(n)\in O(g(n))$ 等价，则称 $O(f(n))$ 与 $O(g(n))$ 相等。完成下列问题：

1. 分别为 (A) $O(n^3)$、(B) $O(n\log n)$、(C) $O(n!)$，从下列候选式中选出所有与之相等的式子；若没有则写 “none”：
   $$\begin{array}{cccc} O(1), & O(n+1), & O(n^2+n+1), & O(n^3+n^2+n+1),\\ O(n^4+n^3), & O(\log n), & O(\log_e n^2), & O((\log_e n)^n),\\ O(2n\log_2 n), & O(e^n), & O\!\left(\left(\frac ne\right)^n\right), & O(2^n),\\ O(n^n). \end{array}$$
2. 对下列两个命题分别判断真伪并证明，其中 $f(n),g(n)$ 均为正函数：
   • $O(f(n)+g(n))=O(\max(f(n),g(n)))$；
   • 若 $f(n)\in O(g(n))$，则 $e^{f(n)}\in O(e^{g(n)})$。

考点

• 渐近时间复杂度：依定义比较多项式、对数、指数与阶乘函数的增长速度，判断相应复杂度集合是否相同。
• 大 $O$ 代数性质：利用常数因子、最高阶项、对数底变换及函数和的主导项证明或否定复杂度等价关系。

Kai

(1)

(A) $O(n^3)$

• $O(n^3 + n^2 + n + 1)$ According to the definition of Big-O notation, the highest order term dominates the growth rate. Therefore, $O(n^3 + n^2 + n + 1)$ and $O(n^3)$ are equivalent.

(B) $O(n \log n)$

• $O(2n \log_2 n)$ In Big-O notation, constant factors and the base of logarithms are ignored, so $O(2n \log_2 n)$ is equivalent to $O(n \log n)$.

(C) $O(n!)$

• None All other formulas in the box either grow slower or faster than $O(n!)$. Therefore, there are no equivalent formulas.

(2)

(A)

Proof:

We need to prove:

$$\lim_{{n \to \infty}} \frac{T(n)}{f(n) + g(n)} < \infty$$

if and only if:

$$\lim_{{n \to \infty}} \frac{T(n)}{\max(f(n), g(n))} < \infty$$

1. If $f(n) \geq g(n)$, then $\max(f(n), g(n)) = f(n)$:

$$f(n) + g(n) \leq 2f(n) \Rightarrow \frac{T(n)}{f(n) + g(n)} \geq \frac{T(n)}{2f(n)}$$

1. If $g(n) \geq f(n)$, then $\max(f(n), g(n)) = g(n)$:

$$f(n) + g(n) \leq 2g(n) \Rightarrow \frac{T(n)}{f(n) + g(n)} \geq \frac{T(n)}{2g(n)}$$

Combining these two cases, we get:

$$\frac{T(n)}{f(n) + g(n)} \geq \frac{T(n)}{2 \max(f(n), g(n))}$$

Conversely, since $\max(f(n), g(n)) \leq f(n) + g(n)$:

$$\frac{T(n)}{\max(f(n), g(n))} \leq \frac{T(n)}{f(n) + g(n)}$$

Therefore:

$$\lim_{{n \to \infty}} \frac{T(n)}{f(n) + g(n)} < \infty \Leftrightarrow \lim_{{n \to \infty}} \frac{T(n)}{\max(f(n), g(n))} < \infty$$

Hence:

$$O(f(n) + g(n)) = O(\max(f(n), g(n)))$$

Therefore, the proposition is true.

(B)

Proof:

Assume $f(n) \in O(g(n))$, meaning there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$,

$$f(n) \leq c \cdot g(n)$$

We need to prove:

$$\lim_{{n \to \infty}} \frac{e^{f(n)}}{e^{g(n)}} < \infty$$

Let's consider $\frac{e^{f(n)}}{e^{g(n)}} = e^{f(n) - g(n)}$.

Since $f(n) \leq c \cdot g(n)$, we get:

$$f(n) - g(n) \leq (c - 1) g(n)$$

So:

$$e^{f(n) - g(n)} \leq e^{(c - 1) g(n)}$$

If $c \leq 1$, then $e^{(c - 1) g(n)} \leq 1$, which is bounded. However, if $c > 1$, $e^{(c - 1) g(n)}$ grows exponentially and is not bounded.

For example, if $f(n) = 2n$ and $g(n) = n$:

$$\frac{e^{2n}}{e^{n}} = e^{2n - n} = e^{n}$$

Clearly, $e^{2n}$ is not in $O(e^{n})$ because its growth rate is much faster. Therefore, in this case, the proposition is false.

Thus, the correct conclusion is that the proposition does not hold.

Knowledge

时间复杂度

Problem-Solving Tips and Information

• When analyzing time complexity, focus on the highest order term.
• In Big-O notation, different bases of logarithms are considered equivalent.
• For combined functions (such as $f(n) + g(n)$), the complexity can be simplified by analyzing the dominant term.

Key Vocabulary

• asymptotic 渐近的
• upper bound 上界
• equivalent 等价的
• exponential 指数的
• limit 极限

References

1. "Introduction to Algorithms" Chapter 3: Growth of Functions
2. "Mathematical Foundations of Computer Science" Chapter 5: Asymptotic Notation