Skip to content

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

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

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