CBMS-2015-07

题目来源：Question 7 日期：2024-06-14 题目主题：CS-算法-时间复杂度

具体题目

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

$$\underset{n\to \infty }{\lim }\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}$$

1. 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))$, then $e^{f(n)}\in O(e^{g(n)})$.

正确解答

1. Find the equivalent formulas

(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. Determine the validity of each proposition

(A) $O(f(n)+g(n))$ and $O(\max (f(n),g(n)))$

Proof:

We need to prove:

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

if and only if:

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

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

$$f(n)+g(n)\le 2f(n)\Rightarrow \frac{T(n)}{f(n)+g(n)}\ge \frac{T(n)}{2f(n)}$$

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

$$f(n)+g(n)\le 2g(n)\Rightarrow \frac{T(n)}{f(n)+g(n)}\ge \frac{T(n)}{2g(n)}$$

Combining these two cases, we get:

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

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

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

Therefore:

$$\underset{n\to \infty }{\lim }\frac{T(n)}{f(n)+g(n)}<\infty \iff \underset{n\to \infty }{\lim }\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) If $f(n)\in O(g(n))$, then $e^{f(n)}\in O(e^{g(n)})$

Proof:

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

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

We need to prove:

$$\underset{n\to \infty }{\lim }\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)\le c\cdot g(n)$, we get:

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

So:

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

If $c\le 1$, then $e^{(c-1)g(n)}\le 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 Points

时间复杂度

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