CBMS-2018-07

题目来源：[[做题/文字版题库/CBMS/2018#Question 7|2018#Question 7]] 日期：2024-07-27 题目主题：CS-算法-时间复杂度分析

解题思路

本题目要求证明 + 某些函数 $f(n)$ 是否属于给定的时间复杂度类别 $O(g(n))$ 和 $\Omega (g(n))$。题目包括三部分，分别涉及指数函数、调和级数和递归函数。通过分析定义和使用适当的数学工具，如极限和主定理，我们可以确定这些函数的时间复杂度。

Solution

Question 1: $f(n)=2^{2n}$

Part (a): Prove whether $f(n)$ is in $O(2^n)$

To prove $f(n)\in O(2^n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0\le 2^{2n}\le c_0\cdot 2^n\text{ for all }n\ge n_0.$$

Notice that $2^{2n}=(2^n{)}^2$. This grows much faster than $2^n$. To find such $c_0$ and $n_0$:

$$2^{2n}\le c_0\cdot 2^n\Rightarrow 2^n\le c_0.$$

For this to hold for all $n\ge n_0$, $c_0$ would have to be infinite, which is not possible. Therefore,

$$f(n)=2^{2n}\notin O(2^n).$$

Part (b): Prove whether $f(n)$ is in $\Omega (2^n)$

To prove $f(n)\in \Omega (2^n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0\le c_0\cdot 2^n\le 2^{2n}\text{ for all }n\ge n_0.$$

Notice that:

$$c_0\cdot 2^n\le 2^{2n}\Rightarrow c_0\le 2^n.$$

For large $n$, $2^n$ grows exponentially, so we can choose any positive constant $c_0$ and it will be less than $2^n$ for sufficiently large $n$. Thus, we can choose $n_0=1$ and any $c_0>0$:

$$f(n)=2^{2n}\in \Omega (2^n).$$

Question 2: $f(n)={\sum }_{i=1}^n\frac{1}{i}$

Part (a): Prove whether $f(n)$ is in $O(\log n)$

To prove $f(n)\in O(\log n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0\le \sum _{i=1}^n\frac{1}{i}\le c_0\log n\text{ for all }n\ge n_0.$$

Let’s use the properties of the harmonic series. We know that:

$$\sum _{i=1}^n\frac{1}{i}\le 1+{\int }_1^n\frac{1}{x}\mathrm{d}x.$$

Evaluating the integral, we get:

$${\int }_1^n\frac{1}{x}\mathrm{d}x=\log n.$$

Thus,

$$\sum _{i=1}^n\frac{1}{i}\le 1+\log n.$$

For sufficiently large $n$, the term $1+\log n$ can be bounded by $c_0\log n$ for some constant $c_0\ge 1$. Hence,

$$f(n)=\sum _{i=1}^n\frac{1}{i}\in O(\log n).$$

Part (b): Prove whether $f(n)$ is in $\Omega (\log n)$

To prove $f(n)\in \Omega (\log n)$, we need to find constants $c_0$ and $n_0$ such that:

$$0\le c_0\log n\le \sum _{i=1}^n\frac{1}{i}\text{ for all }n\ge n_0.$$

We can compare the harmonic series with the integral from below. Specifically,

$$\sum _{i=1}^n\frac{1}{i}\ge {\int }_1^{n+1}\frac{1}{x}\mathrm{d}x.$$

Evaluating the integral, we get:

$${\int }_1^{n+1}\frac{1}{x}\mathrm{d}x=\log (n+1).$$

Thus,

$$\sum _{i=1}^n\frac{1}{i}\ge \log (n+1).$$

For sufficiently large $n$, $\log (n+1)$ can be bounded from below by $c_0\log n$ for some constant $c_0>0$. Thus, we can choose $c_0=1$ and $n_0=1$:

$$f(n)=\sum _{i=1}^n\frac{1}{i}\in \Omega (\log n).$$

Question 3: $f(n)$ satisfies $f(1)=1$ and $f(n)=f(\lfloor n/2\rfloor )+n$ for $n\ge 2$

Part (a): Prove whether $f(n)$ is in $O(n)$

To analyze this, we use the Master Theorem for divide-and-conquer recurrences. Here, the recurrence is:

$$f(n)=f(\lfloor n/2\rfloor )+n.$$

This fits the form $f(n)=af(n/b)+g(n)$ with $a=1$, $b=2$, and $g(n)=n$. The Master Theorem states:

1. If $g(n)=O(n^c)$ where $c<{\log }_{b}a$, then $f(n)=\Theta (n^{{\log }_{b}a})$.
2. If $g(n)=\Theta (n^{{\log }_{b}a})$, then $f(n)=\Theta (n^{{\log }_{b}a}\log n)$.
3. If $g(n)=\Omega (n^c)$ where $c>{\log }_{b}a$, and if $ag(n/b)\le kg(n)$ for some $k<1$ and sufficiently large $n$, then $f(n)=\Theta (g(n))$.

In this case, ${\log }_{b}a={\log }_{2}1=0$, and $g(n)=n$. Since $n=\Omega (n^0)$ and $g(n)=n$, case 3 of the Master Theorem applies, giving us:

$$f(n)=\Theta (n).$$

Thus,

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

Part (b): Prove whether $f(n)$ is in $\Omega (n^2)$

We already have from the Master Theorem that $f(n)=\Theta (n)$. Therefore, $f(n)$ is not $\Omega (n^2)$, because $\Theta (n)$ implies both upper and lower bounds $O(n)$ and $\Omega (n)$.

Thus,

$$f(n)\notin \Omega (n^2).$$

知识点

递归主定理复杂度分析

重点词汇

• Asymptotic bounds 渐近界
• Master Theorem 主定理
• Harmonic series 调和级数
• Exponential function 指数函数
• Recurrence 递归

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press. Chapter 3: Growth of Functions, and Chapter 4: Divide-and-Conquer.
2. Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser. Data Structures and Algorithms in Java, 6th Edition. Wiley. Chapter 5: Recursion.