算法导论4.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

4.1-1

令$n’=2^{\lceil\lg n\rceil}$。那么不难发现，有$\dfrac{1}{2}<\dfrac{n}{n’}\le 1$成立。

为矩阵$A,B$补$0$到$n’$的大小，那么可以得到新矩阵$A’,B’$。也就是说，对于矩阵$A’$中的新元素$a_{ij}’$，有：

$a{i,j}’=
\left {\begin{aligned}
&a{i,j} & & \text{if}\quad i\le n \land j\le n \
&0 & & \text{if}\quad i> n \lor j> n \
\end{aligned}\right.$

矩阵$B’$同理。

递推式仍然为$T’(n)=8T’(n/2)+\Theta(1)$。

由于传统算法MATRIX-MULTIPLY-RECURSIVE的时间复杂度是$T(n)=\Theta(n^3)$，因此$\exists c_1,c_2,n_0\in \mathbb{R}^{+},\forall n’\ge n_0,0\le c_1n’^3\le f(n’)\le c_2n’^3$。回代$n$，得到$0\le \dfrac{c_1}{8}\cdot n^3\le f(n)\le c_2n^3$。因此$T’(n)=\Theta(n^3)$。

4.1-2

使用这个程序作为子程序计算$kn \times n$和$n\times kn$大小的矩阵相乘需要花费$\Theta(k^2n^3)$的时间。如果是$n \times kn$和$kn\times n$大小的矩阵相乘，则需要花费$\Theta(kn^3)$的时间。

4.1-3

由于涉及到矩阵的复制操作，因此每次调用都会有$\Theta(n^2)$的操作时间。

因此运行时间的递推式就写成$T(n)=8T(n/2)+\Theta(n^2)$。

根据主定理，$a=8,b=2,\log _b a=3$.

因此根据第一个条件，$T(n)=\Theta(n^3)$。

4.1-4

1
2
3
4
5
6
7
8
9
10
11
12
MATRIX-ADD-RECURSIVE(A, B, C, n)
  if n == 1
  // Base case.
    c11 = c11 + a11 + b11
    return
  // Divide.
  partition A, B, and C into n/2 × n/2 submatrices A11, A12, A21, A22; B11, B12, B21, B22; and C11, C12, C21, C22; respectively
   // Conquer.
  MATRIX-ADD-RECURSIVE(A11, B11, C11, n/2)
  MATRIX-ADD-RECURSIVE(A12, B12, C12, n/2)
  MATRIX-ADD-RECURSIVE(A21, B21, C21, n/2)
  MATRIX-ADD-RECURSIVE(A22, B22, C22, n/2)

如果使用的方法是直接基于索引的计算，那么运行时间的递推式就写成$T(n)=4T(n/2)+\Theta(1)$。

根据主定理，$a=4,b=2,\log _b a=2$.

因此根据第一个条件，$T(n)=\Theta(n^2)$。

如果使用的方法是直接基于索引的计算，那么运行时间的递推式就写成$T(n)=4T(n/2)+\Theta(n^2)$。

因此根据第二个条件，得到$k=0$，最终$T(n)=\Theta(n^{2}\lg ^1 n)=\Theta(n^2 \lg n)$。