Homework04.tex

\section{0312}
\begin{questions}

    \question 证明$$\sum_{k=1}^n {\frac{1}{k}} = \Theta(\log n)$$
    \begin{solution}
        \begin{proof}
            由$\frac{1}{k}$单调递减\begin{align*}
                \int_{1}^{n+1} {\frac{1}{x}} \mathrm{d}x
                                      & \leq \sum_{k=1}^n {\frac{1}{k}} \leq 1 + \int_1^{n} {\frac{1}{x}} \mathrm{d}x \\
                \ln{(n+1)} - \ln{1}   & \leq \sum_{k=1}^n {\frac{1}{k}} \leq 1 + \ln{n} - \ln{1}                      \\
                \ln{(n)} < \ln{(n+1)} & \leq \sum_{k=1}^n {\frac{1}{k}} \leq 1 + \ln{n}
            \end{align*}
            所以有\begin{align*}
                \Omega(\log{n}) = \sum_{k=1}^n {\frac{1}{k}} & = O(\log{n})
            \end{align*}
            即$$
                \sum_{k=1}^n {\frac{1}{k}} = \Theta(\log{n})
            $$
        \end{proof}
    \end{solution}

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    \question 设有如下递推关系 $$
        T(n) = \begin{cases}
            T(\frac{n}{2}) + 1 & , n\text{为偶数} \\
            2T(\frac{n-1}{2})  & , n\text{为奇数}
        \end{cases}
    $$其中$T(1) = 1$
    \begin{parts}
        \part 证明当$n=2^k$时，$T(n)=O(\log n)$
        \begin{solution}
            \begin{proof}
                \begin{align*}
                    T(n) = T(2^k) & = T(\frac{n}{2}) + 1 = T(2^{k-1}) + 1 \\
                                  & = T(2^{k-2}) + 2 = \dots              \\
                                  & = T(1) + k-1 = k = \log n
                \end{align*}
                所以$$ T(n) = O(\log n) $$
            \end{proof}
        \end{solution}

        \part 证明存在无穷集合$X$，当$n \in X$时，$T(n)=\Omega (n)$
        \begin{solution}
            令$a_1 = 1$, $a_n = 2 a_{n-1} + 1 \Rightarrow a_n = 2^{n}-1$，
            则无穷集合$X = \left\{ 2^{k} - 1 \mid k \in \mathbb{N}^* \right\}$。

            \begin{proof}
                \begin{align*}
                    T(n) = T(2^k-1) & = 2 \cdot T(\frac{n-1}{2}) + 1 = 2 \cdot T(2^{k-1} - 1) \\
                                    & = 4 \cdot T(2^{k-2}-1) = \dots                          \\
                                    & = 2^{k-1} \cdot T(2-1) = 2^{k-1}
                \end{align*}
                $\exists c = \frac{1}{2}, N = 1$使得$\forall n > N, n \in X$
                $$T(n) = T(2^k-1) = 2^{k-1} > 2^{k-1} - \frac{1}{2} = \frac{2^k-1}{2} = \frac{n}{2}$$
                所以$$T(n) = \Omega(n)$$
            \end{proof}
        \end{solution}

        \part 以上两个结论说明了什么？
        \begin{solution}
            一个算法在输入具有不同特征时，可能具有不同的时间复杂度。

            最佳状况和最差状况可能有不同的时间复杂度。
        \end{solution}
    \end{parts}
\end{questions}