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

标签：

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

Author

zephyr, 祭音Myyura

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)})$。

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 functions in the box grow either slower or faster than $n!$. In particular, Stirling’s formula gives $n!/(n/e)^n\sim\sqrt{2\pi n}\to\infty$, so $O((n/e)^n)$ is not equal to $O(n!)$.

(2)

(A)

With the stated definition requiring an ordinary limit, the proposition is false. For integer $n>1$, take

$$f(n)=n,\qquad g(n)=n\bigl(2+(-1)^n\bigr),\qquad T(n)=f(n)+g(n).$$

Both $f$ and $g$ are positive and $T(n)/(f(n)+g(n))=1$. However,

$$\frac{T(n)}{\max(f(n),g(n))} =\begin{cases}4/3,&n\text{ even},\\2,&n\text{ odd},\end{cases}$$

has no limit. Thus the two classes defined using that limit are not equal.

Under the usual Big-O definition by an eventual upper bound, the proposition is true, because

$$\max(f,g)\le f+g\le2\max(f,g).$$

These inequalities imply that $T/(f+g)$ is eventually bounded if and only if $T/\max(f,g)$ is eventually bounded.

(B)

The proposition is false. Take $f(n)=2n$ and $g(n)=n$. Then

$$\frac{f(n)}{g(n)}=2, \qquad \frac{e^{f(n)}}{e^{g(n)}}=e^n\longrightarrow\infty.$$

Hence $f\in O(g)$ but $e^f\notin O(e^g)$.

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

Reference

• 東京大学 CBMS 公式過去問