时间复杂度的渐近分析

个人思路，仅供参考

1.时间复杂度的渐近分析

以下每个小题中两个函数分别为$ f(n) $和$ g(n) $。 在渐近分析中, 可以写成$ f(n) = \ldots(g(n)) $的形式。请计算并选择相应的$ \mathcal{O} $、$ \Theta $、$ \Omega $符号。

(1) $ f(n) = n^{\frac{1}{2}} $ $ g(n) = (\log 2 n)^5 $

$$\begin{equation} \begin{aligned} \lim _{n \rightarrow +\infty} \frac{(\log 2 n)^5}{n^{\frac{1}{2}}} & \triangleq \lim _{n \rightarrow +\infty} \frac{5 \times 2 \cdot(\log 2 n)^4 \cdot \frac{1}{2 n \cdot \ln 2}}{\frac{1}{2} n^{-\frac{1}{2}}} \\ & = \lim _{n \rightarrow +\infty} \frac{5 \cdot(\log 2 n)^4 \cdot \frac{1}{\ln 2}}{\frac{1}{2} n^{\frac{1}{2}}} \\ & \triangleq \lim _{n \rightarrow +\infty} \frac{5 \times 4 \times 2 \cdot(\log 2 n)^3 \cdot \frac{1}{2 n} \cdot \frac{1}{\ln 2} \cdot \frac{1}{\ln 2}}{\frac{1}{2} \times \frac{1}{2} n^{-\frac{1}{2}}} \\ & = \lim _{n \rightarrow +\infty} \frac{5 \times 4 \cdot(\log 2 n)^3 \cdot (\frac{1}{\ln 2})^2}{\frac{1}{2} \times \frac{1}{2} n^{\frac{1}{2}}} \\ & \triangleq \ldots \\ & \triangleq \lim _{n \rightarrow +\infty} \frac{5 \times 4 \times 3 \times 2 \cdot (\frac{1}{\ln 2})^5}{(\frac{1}{2})^5 \cdot n^{\frac{1}{2}}} \\ & = 0 \\ \end{aligned} \end{equation}$$

上式中，等号上的△表示此等号右方使用了一次洛必达法则(L’Hospital Rule)。

$$\begin{equation} \lim _{n \rightarrow +\infty} \frac{(\log 2 n)^5}{n^{\frac{1}{2}}} = 0 \end{equation}$$

即：

$$\begin{equation} n^{\frac{1}{2}} = \Omega((\log 2 n)^5) \end{equation}$$

(2) $ f(n) = (\log n)^{2 \log n} $ $ g(n) = n^3 $

首先利用换元法，令$ \log n = t $ ， 则$ n = 2^t $ ， $ f(n) = t^{2t} $ ， $ g(n) = 2^{3t} $

则：

$$\begin{equation} \begin{aligned} \lim _{n \rightarrow +\infty} \frac{n^3}{(\log n)^{2 \log n}} & = \lim _{t \rightarrow +\infty} \frac{2^{3t}}{t^{2t}} \\ & = \lim _{t \rightarrow +\infty} (\frac{8}{t^2})^t \\ & = 0 \\ \end{aligned} \end{equation}$$ $$\begin{equation} \lim _{n \rightarrow +\infty} \frac{n^3}{(\log n)^{2 \log n}} = 0 \end{equation}$$

即：

$$\begin{equation} (\log n)^{2 \log n} = \Omega(n^3) \end{equation}$$

(3) $ f(n) = n^2 $ $ g(n) = 3^{2 \log n} $

此题类似于(2)，利用换元法，令$ \log n = t $ ， 则$ n = 2^t $ ， $ f(n) = 2^{2t} $ ， $ g(n) = 3^{2t} $

则：

$$\begin{equation} \begin{aligned} \lim _{n \rightarrow +\infty} \frac{3^{2 \log n}}{n^2} & = \lim _{t \rightarrow +\infty} \frac{3^{2t}}{2^{2t}} \\ & = \lim _{t \rightarrow +\infty} 1.5^{2t} \\ & = +\infty \\ \end{aligned} \end{equation}$$ $$\begin{equation} \lim _{n \rightarrow +\infty} \frac{3^{2 \log n}}{n^2} = +\infty \end{equation}$$

即：

$$\begin{equation} n^2 = \mathcal{O}(3^{2 \log n}) \end{equation}$$

(4) $ f(n) = n!! $ $ g(n) = 2^n $

• n为偶数时

  $$\begin{equation} \begin{aligned} \lim _{n \rightarrow +\infty} \frac{2^n}{n!!} & = \lim _{t \rightarrow +\infty} \frac{4^{\frac{n}{2}}}{n (n - 2) (n - 4) \ldots 4 \times 2} \\ & = \lim _{n \rightarrow +\infty} \frac{4}{n} \cdot \frac{4}{n - 2} \cdot \frac{4}{n - 4} \ldots \frac{4}{4} \times \frac{4}{2} \\ \end{aligned} \end{equation}$$

  观察上式，由于$ n \rightarrow +\infty $ ， $ \frac{4}{n} \rightarrow +\infty $且除最后两项外其他所有项均小于1

  由此可得：

  $$\begin{equation} \lim _{n \rightarrow +\infty} \frac{2^n}{n!!} = 0 \end{equation}$$

• n为奇数时

  用相同方法

  $$\begin{equation} \begin{aligned} \lim _{n \rightarrow +\infty} \frac{2^n}{n!!} & = \lim _{t \rightarrow +\infty} \frac{4^{\frac{n}{2}}}{n (n - 1) (n - 3) \ldots 3 \times 1} \\ & = \lim _{n \rightarrow +\infty} \frac{4}{n} \cdot \frac{4}{n - 1} \cdot \frac{4}{n - 3} \ldots \frac{4}{3} \times \frac{4}{1} \\ \end{aligned} \end{equation}$$

  观察上式，由于$ n \rightarrow +\infty $ ， $ \frac{4}{n} \rightarrow +\infty $且除最后两项外其他所有项均小于1

  由此可得：

  $$\begin{equation} \lim _{n \rightarrow +\infty} \frac{2^n}{n!!} = 0 \end{equation}$$

  综上：

  $$\begin{equation} \lim _{n \rightarrow +\infty} \frac{2^n}{n!!} = 0 \end{equation}$$

  即：

  $$\begin{equation} n!! = \Omega(2^n) \end{equation}$$

2.递归算法的时间复杂度

参考第1.3小节里的推导过程和结果，完成以下小题：

(1) 如果$ f(n)=n^{\log _b a+\epsilon} $ ，且$ 0<\epsilon \ll 1 $。请推导$T(n)$。

根据第1.3小节推导内容，把规模大小为的问题平均分成b(≥2)份，然后在这些子问题上迭代地使用分治算法。在构造问题的解时，我们选择$a \in{1, \cdots, b}$个子问题的解进行合并。此时子问题解的合并过程耗时为$ \mathcal{O}(f(n)) $。则递归算法的时间复杂度函数$ T(n) $可以写成

$$\begin{equation} T(n)=a T\left(\frac{n}{b}\right)+\mathcal{O}(f(n)) \end{equation}$$

递推公式以得到更小的n，直到到达递归基，也就是对应着n=1的情形。

$$\begin{equation} \begin{aligned} T(n) & =a T\left(\frac{n}{b}\right)+\mathcal{O}(f(n)) \\ & =a\left[a T\left(\frac{n}{b^2}\right)+\mathcal{O}\left(f\left(\frac{n}{b}\right)\right)\right]+\mathcal{O}(f(n)) \\ & =a^2 T\left(\frac{n}{b^2}\right)+a \mathcal{O}\left(f\left(\frac{n}{b}\right)\right)+\mathcal{O}(f(n)) \\ & =a^2\left[a T\left(\frac{n}{b^3}\right)+\mathcal{O}\left(f\left(\frac{n}{b^2}\right)\right)\right]+a \mathcal{O}\left(f\left(\frac{n}{b}\right)\right)+\mathcal{O}(f(n)) \\ & =a^3 T\left(\frac{n}{b^3}\right)+a^2 \mathcal{O}\left(f\left(\frac{n}{b^2}\right)\right)+a \mathcal{O}\left(f\left(\frac{n}{b}\right)\right)+\mathcal{O}(f(n)) \\ & =\cdots \\ & =a^t T\left(\frac{n}{b^t}\right)+\sum_{i=0}^{t-1} a^i \mathcal{O}\left(f\left(\frac{n}{b^i}\right)\right) \end{aligned} \end{equation}$$

上式中，$t \in{0, 1, 2, \cdots }$为递推步骤的序号。

对于足够大的t,我们有n/b=1,即$ t = \log _{b} n $。此时对应着算法操作到了单个元素的层次。同时我们假定递推基$ T(1) = \Theta(1) $，即为常数操作时间。则：

$$\begin{equation} T(n)=a^{\log _b n} T(1)+\sum_{i=0}^{\log _b n-1} a^i \mathcal{O}\left(f\left(\frac{n}{b^i}\right)\right) \end{equation}$$

利用等式

$$\begin{equation} a^{\log _b n}=n^{\log _n a \cdot \log _b n}=n^{\frac{\ln a}{\ln n} \cdot \frac{\ln n}{\ln b}}=n^{\frac{\ln a}{\ln b}}=n^{\log _b a} \end{equation}$$

得到

$$\begin{equation} T(n)=n^{\log _b a} T(1)+\sum_{i=0}^{\log _b n-1} a^i \mathcal{O}\left(f\left(\frac{n}{b^i}\right)\right) \end{equation}$$

代入$ f(n) = n^{\log _b a+\epsilon} $得

$$\begin{equation} \begin{aligned} T(n) & =n^{\log _b a} T(1)+\sum_{i=0}^{\log _b n-1} a^i \mathcal{O}\left[\left(\frac{n}{b^i}\right)^{\log _b a+\epsilon}\right] \\ & =n^{\log _b a} T(1)+\sum_{i=0}^{\log _b n-1} a^i \mathcal{O}\left[\frac{n^{\log _b a+\epsilon}}{b^{i\left(\log _b a+\epsilon\right)}}\right] \\ & =n^{\log _b a} T(1)+\sum_{i=0}^{\log _b n-1} \not a^i \mathcal{O}\left(\frac{n^{\log _b a+\epsilon}}{\not a^i \cdot b^{i \epsilon}}\right) \\ & =n^{\log _b a} T(1)+\sum_{i=0}^{\log _b n-1} \mathcal{O}\left(\frac{n^{\log _b a+\epsilon}}{b^{i \epsilon}}\right) \\ & =n^{\log _b a} T(1)+\mathcal{O}\left(n^{\log _b a+\epsilon} \cdot \sum_{i=0}^{\log _b n-1} b^{-i \epsilon}\right) \end{aligned} \end{equation}$$

上式中的级数求和为

$$\begin{equation} \sum_{i=0}^{\log _b n-1} b^{-i \epsilon}=\frac{1 - b^{-\epsilon \log _b n}}{1 - b^{-\epsilon}}=\frac{1 - n^{-\epsilon}}{1 - b^{-\epsilon}} \end{equation}$$

因为$ -\epsilon < 0 $ ， 当n很大时， $ \lim _{n \rightarrow +\infty} (1 - n^{-\epsilon}) = 1 $ ， 则：

$$\begin{equation} \begin{aligned} T(n) & =n^{\log _b a} T(1)+\mathcal{O}\left(n^{\log _b a+\epsilon} \cdot \frac{1}{1 - b^{-\epsilon}} \right) \\ & =n^{\log _b a} T(1)+\mathcal{O}\left(n^{\log _b a} \cdot (b - 1)\right) \\ & =\mathcal{O}\left(n^{\log _b a}\right) \end{aligned} \end{equation}$$

(2) 在二分查找算法里，如果$ T(n)=T(\frac{n}{2}) + c $ ，其中c为某一常整数。请推导$T(n)$

$$\begin{equation} \begin{aligned} T(n) & =T\left(\frac{n}{2}\right)+\mathcal{O}(c) \\ & =T\left(\frac{n}{4}\right)+\mathcal{O}(c)+\mathcal{O}(c) \\ & =T\left(\frac{n}{8}\right)+\mathcal{O}(c)+\mathcal{O}(c)+\mathcal{O}(c) \\ & =\cdots \\ & =T\left(\frac{n}{2^t}\right)+\sum_{i=0}^{t-1} 1^i \mathcal{O}(c) \end{aligned} \end{equation}$$

上式中，$t \in{0, 1, 2, \cdots }$为递推步骤的序号。

对于足够大的t,我们有$ \frac{n}{2^t}=1 $ ,即$ t = \log n $。此时对应着算法操作到了单个元素的层次。同时我们假定递推基$ T(1) = \Theta(1) $，即为常数操作时间。则：

$$\begin{equation} \begin{aligned} T(n) &=T(1)+\sum_{i=0}^{\log n-1} 1^i \mathcal{O}(c) \\ & =T(1)+\log n \mathcal{O}\left(c\right) \\ & =\mathcal{O}\left(\log n\right) \end{aligned} \end{equation}$$

对于上式中的级数求和

由于1的任意次方都是1，上式中的$ \sum_{i=0}^{\log n-1} 1^i $ 可视作0到$ \log _2 n-1 $ ，一共$ \log n $个$ \mathcal{O}(1) $相加。

二分查找算法的递归树一共有$ \log n $层，每一层时间复杂度为c，时间复杂度即为$ \mathcal{O}\left(\log n\right) $

(3) 在归并排序算法里，如果$ T(n) = 2 T(\frac{n}{2}) + cn + d $ ，其中c和d均为常整数。请推导$T(n)$

$$\begin{equation} \begin{aligned} T(n) & =2 T\left(\frac{n}{2}\right)+\mathcal{O}(cn)+\mathcal{O}(d) \\ & =2\left[2 T\left(\frac{n}{2^2}\right)+\mathcal{O}(c\frac{n}{2})+\mathcal{O}(d)\right]+\mathcal{O}(cn)+\mathcal{O}(d) \\ & =2^2 T\left(\frac{n}{2^2}\right)+\mathcal{O}(cn)+2\mathcal{O}(d)+\mathcal{O}(cn)+\mathcal{O}(d) \\ & =\cdots \\ & =2^t T\left(\frac{n}{2^t}\right)+\sum_{i=0}^{t-1} 1^i \mathcal{O}(cn)+\sum_{i=0}^{t-1} 2^i \mathcal{O}(d) \end{aligned} \end{equation}$$

上式中，$t \in{0, 1, 2, \cdots }$为递推步骤的序号。

对于足够大的t,我们有$ \frac{n}{2^t}=1 $ ,即$ t = \log n $。此时对应着算法操作到了单个元素的层次。同时我们假定递推基$ T(1) = \Theta(1) $，即为常数操作时间。则：

$$\begin{equation} T(n)=2^{\log n} T(1)+\sum_{i=0}^{\log n-1} 1^i \mathcal{O}(cn)+\sum_{i=0}^{\log n-1} 2^i \mathcal{O}(d) \end{equation}$$

利用等式

$$\begin{equation} a^{\log _b n}=n^{\log _n a \cdot \log _b n}=n^{\frac{\ln a}{\ln n} \cdot \frac{\ln n}{\ln b}}=n^{\frac{\ln a}{\ln b}}=n^{\log _b a} \end{equation}$$

得到

$$\begin{equation} \begin{aligned} T(n) &=n^{\log 2} T(1)+\sum_{i=0}^{\log n-1} 1^i \mathcal{O}(cn)+\sum_{i=0}^{\log n-1} 2^i \mathcal{O}(d) \\ & =n T(1)+\log n \mathcal{O}\left(cn\right)+(n - 1) \mathcal{O}(d) \\ & = \mathcal{O}(n\log n) \end{aligned} \end{equation}$$

对于上式中的级数求和

由于1的任意次方都是1，上式中的$ \sum_{i=0}^{\log n-1} 1^i $ 可视作0到$ \log _2 n-1 $ ，一共$ \log n $个$ \mathcal{O}(1) $相加。

$$\begin{equation} \sum_{i=0}^{\log n-1} 2^i=\frac{2^{\log n}-1}{2-1}=n-1 \end{equation}$$

归并排序算法的递归树一共有$ \log n $层，每一层时间复杂度为n，时间复杂度即为$ \mathcal{O}(n\log n) $