Homework13-1.tex

\section{0511}\label{sec:0511}
\begin{questions}
    \question 设计算法求出$n$个矩阵$M_1, M_2, \dots ,M_n$相乘最多需要多少次乘法，请给出详细的算法描述和时间复杂性

    \begin{solution}
        给定$n+1$个正整数$c_0,c_1, \dots , c_{n}$，
        其中$c_{i-1}$ 和 $c_{i}$ 为矩阵$M_i$的行数和列数，$1 \le i \le n$。

        记$M_{ij}$为$M_iM_{i+1} \dots M_j$的乘积，$Q(i,j)$为计算$M_{ij}$所需要的最多乘法数量，则
        \[
            Q(i,j) = \begin{cases}
                \max_{i \le k < j}{ \left\{ Q(i, k) + Q(k+1, j) + c_{i-1} c_k c_{j} \right\} } & , i < j \\
                0                                                                              & , i = j
            \end{cases}
        \]
        \textbf{伪代码见算法\ref{alg:0511:1}}，算法的时间复杂度为$O(n^3)$。
    \end{solution}

    \begin{algorithm}[!htp]
        \caption{矩阵最多乘法次数}\label{alg:0511:1}
        \begin{algorithmic}[1]
            \Require {$n+1$个正整数$c[0 \dots n]$}
            \Ensure {最大乘法次数}
            \State $Q[1 \dots n][1 \dots n] \gets \left\{0\right\}$
            \For {$j \gets 2$ to $n$}
            \For {$i \gets j-1$ down to $1$}
            \State $precompute \gets c[i-1]c[j]$
            \For {$k \gets i$ to $j-1$}
            \State $t \gets Q[i][k] + Q[k+1][j] + c[k] \cdot precompute$
            \State $Q[i][j] \gets t$ if $Q[i][j] < t$
            \EndFor
            \EndFor
            \EndFor
            \State \Return $Q[1][n]$
        \end{algorithmic}
    \end{algorithm}

    \question 设有算法$A$能够在$O(i)$时间内计算一个$i$次多项式和一个$1$次多项式的乘积，
    算法$B$能够在$O(i \log i)$时间内计算两个$i$次多项式的乘积。
    现给定$d$个整数$n_1,n_2, \dots ,n_d$，设计算法求出满足$P(n_1)=P(n_2)= \dots =P(n_d)=0$
    且最高次项系数为$1$的$d$次多项式$P(x)$，并给出算法的时间复杂性。

    \begin{solution}
        满足$P(n_1)=P(n_2)= \cdots =P(n_d)=0$且最高次项系数为$1$的$d$次多项式$P(x)$为
        \[
            P(x) = (x-n_1)(x-n_2) \cdots (x-n_d)
        \]

        记$Q(i,j) = (x-n_i) \cdots (x-n_j)$，则$P(x) = Q(1,d)$
        \[
            Q(i,j) = \begin{cases}
                A(Q(i,j-1), (x-n_j))                 & , j-i+1 \equiv 1 \bmod 2 \\
                B(Q(i,(i+j-1)/2), Q((i+j-1)/2+1, j)) & , j-i+1 \equiv 0 \bmod 2
            \end{cases}
        \]

        \textbf{伪代码见算法\ref{alg:0511:2}}

        \newcommand{\pp}[1]{ \left( #1 \right) }
        \newcommand{\pb}[1]{ \left[ #1 \right] }
        \newcommand{\pT}[1]{ T\left( #1 \right) }
        \newcommand{\pO}[1]{ O\left( #1 \right) }

        设该算法运行所需时间为$T(d)$，则\[
            T(d) = \begin{cases}
                1                                                     & , d = 2              \\
                \pT{d-1} + \pO{d-1}                                   & , d \equiv 1 \bmod 2 \\
                2\pT{\frac{d}{2}} + \pO{\frac{d}{2} \log \frac{d}{2}} & , d \equiv 0 \bmod 2
            \end{cases}
        \]

        \begin{itemize}
            \item 当$d = 2^k$时，
                  \begin{align*}
                      \pT{2^k}
                      = & 2 \pT{ 2^{k-1} } + \pO{ (k-1)2^{k-1} }                    \\
                      = & 2^2 \pT{ 2^{k-2} } + \pO{ 2(k-2) 2^{k-2} +(k-1) 2^{k-1} } \\
                      = & 2^2 \pT{ 2^{k-2} } + \pO{ \pb{ (k-2)+(k-1) } 2^{k-1} }    \\
                      = & 2^{k-1} \pT{2} + \pO{ \sum_{i=1}^{k-1} (k-i) 2^{k-1} }    \\
                      = & 2^{k-1} + \pO{ k^{2} 2^{k-1} } = \pO{ d \cdot \log^2 d }
                  \end{align*}
            \item 当$d = 2^k - 1$时，记$u_k = 2^k - 1$，且有$u_k - 1 = 2u_{k-1}$
                  \begin{align*}
                      \pT{2^k - 1} = \pT{u_k}
                      = & \pT{ u_k-1 } + \pO{ u_k-1 } = \pT{ 2 u_{k-1} } + \pO{ 2 u_{k-1} }                                                      \\
                      = & 2 \pT{ u_{k-1} } + \pO{ u_{k-1} \log\pp{ u_{k-1} } } + \pO{ 2 u_{k-1} }                                                \\
                      = & 2^2 \pT{ u_{k-2} } + \pO{ 2 u_{k-2} \log\pp{ u_{k-2} } + u_{k-1} \log\pp{ u_{k-1} } } + \pO{ 2^2 u_{k-2} + 2 u_{k-1} } \\
                      = & 2^{k-2} \pT{ u_{2} } + \pO{ \sum_{i=2}^{k-1} 2^{k-i-1}u_{i} \log\pp{ u_{i} } } + \pO{ \sum_{i=2}^{k-1} 2^{k-i} u_{i} } \\
                      = & \pO{ 3 \cdot 2^{k-2} } + \pO{ \sum_{i=2}^{k-1} 2^{k-i-1}\pp{2^i-1} i + \sum_{i=2}^{k-1} 2^{k-i} \pp{2^i-1} }           \\
                      %   = & 2^{k-2} \pT{ 3 } + \pO{ \sum_{i=2}^{k-1} 2^{k-i-1}\pp{2^i-1} \log\pp{ u_{i} } + \sum_{i=2}^{k-1} 2^{k-i} \pp{2^i-1} }                               \\
                      %   = & 2^{k-2} \pp{ \pT{ 2 } + \pO{ 2 } } + \pO{ \sum_{i=2}^{k-1} \pp{2^{k-1}-2^{k-i-1}} \log\pp{ u_{i} } + \sum_{i=2}^{k-1} \pp{2^{k}-2^{k-i}} }                 \\
                      %   = & \pO{ 3 \cdot 2^{k-2} } + \pO{ (k-2) 2^k + \sum_{i=2}^{k-1} 2^{k-1}\log\pp{ u_{i} } - \sum_{i=2}^{k-1} 2^{k-i-1}\log\pp{ u_{i} } - \sum_{i=1}^{k-2} 2^i } \\
                      %   = & \pO{ 2^{k-2} + (k-2) 2^k + 2 } + \pO{ \sum_{i=2}^{k-1} i \cdot 2^{k-1} - \sum_{i=2}^{k-1} i \cdot 2^{k-i-1} } \\
                      %   = & \pO{ 2^{k-2} + (k-2) 2^k + 2 } + \pO{ \pb{ 2^{k-2}\left(k^{2}-k-2\right) } - \pb{ -k+3 \times 2^{k-2}-1 } } \\
                      = & \pO{ 2^{k-2} k^{2}+3 \times 2^{k-2} k+k-3 \times 2^{k}+3 } = \pO{ 2^k k^2 } = \pO{ d \log^2 d }
                  \end{align*}
        \end{itemize}
    \end{solution}

    \begin{algorithm}[!htp]
        \caption{零点多项式}\label{alg:0511:2}
        \begin{algorithmic}[1]
            \Require {$d$个整数$n[1 \dots d]$}
            \Ensure {多项式}

            \Procedure{Q}{$n[1 \dots d]$}
            \If{ $d = 1$ }
            \State \Return $(-n[d], 1)$ \Comment{$x-n_d$}
            \ElsIf{ $d \equiv 0 \bmod 2$ }
            \State $P_1 \gets \Call{Q}{n[1 \dots d/2]}$
            \State $P_2 \gets \Call{Q}{n[d/2 + 1 \dots d]}$
            \State \Return $\Call{GivenAlgoB}{P_1,P_2}$
            \Else
            \State $P_1 \gets \Call{Q}{n[1 \dots d-1]}$
            \State $P_2 \gets \Call{Q}{n[d \dots d]}$
            \State \Return $\Call{GivenAlgoA}{P_1,P_2}$
            \EndIf
            \EndProcedure

            \State \Return $\Call{Q}{n}$
        \end{algorithmic}
    \end{algorithm}

    \question 将正整数$n$表示成一系列正整数之和：$n=n_1+n_2+ \dots +n_k$，
    其中$n_1 \ge n_2 \ge \dots \ge n_k \ge 1$，$k \ge 1$。
    正整数$n$的这种表示称为正整数$n$的划分，例如正整数6有如下11种不同的划分：
    \begin{center}
        \begin{tabular}{ccc}
            $ 6 $           &             &               \\
            $ 5+1 $         &             &               \\
            $ 4+2 $         & $ 4+1+1 $   &               \\
            $ 3+3 $         & $ 3+2+1 $   & $ 3+1+1+1 $   \\
            $ 2+2+2 $       & $ 2+2+1+1 $ & $ 2+1+1+1+1 $ \\
            $ 1+1+1+1+1+1 $ &             &               \\
        \end{tabular}
    \end{center}
    设计算法求正整数$n$的不同划分个数并证明其时间复杂性为$\Theta(n^2)$。

    \begin{solution}
        记$Q(n, m)$为最大数为$m$的$n$的所有划分，
        即$m = n_1 \ge n_2 \ge \dots \ge n_k \ge 1$。
        当一个划分中最大的数为$k$时，划分中剩余的部分为$Q(n-k,k)$，
        使用动态规划求解。
        \[
            P(n) = \bigcup_{1 \le m \le n} Q(n, m)
        \]其中
        \[
            Q(n, m) = \begin{cases}
                \bigcup_{1 \le k \le m, k<n} {\left\{ k \right\} \times Q(n-k, k) } & n > m \ge 1 \\
                \left\{ \left\{ n \right\} \right\}                                 & n = m       \\
            \end{cases}
        \]

        \textbf{代码见算法\ref{alg:0511:3}}

        求解$P(n)$，需要求解$\frac{n(n-1)}{2}$个子问题$Q$，所以时间复杂度为$\Theta(n^2)$
    \end{solution}

    \begin{algorithm}[!htp]
        \caption{正整数分划}\label{alg:0511:3}
        \inputminted{python}{alg-0511-03.py}
    \end{algorithm}


\end{questions}