算法概论(DPV)习题解答——第0章序言

书籍介绍：

https://book.douban.com/subject/3155710/

配套课程：

CS170（伯克利），CS161（斯坦福）

github仓库：

https://github.com/Doraemonzzz/Algorithm-DPV

参考资料：

https://www.cnblogs.com/atyuwen/archive/2009/11/10/algorithmsexercisessolution.html

很久以前就买了这本书，一直没怎么翻，今天争取完成重点部分的习题解答，部分习题还是挺难的。

这次回顾第0章，序言。

第0章

4

(a)

记

$\begin{aligned} A& = \left[ \begin{matrix} a_{11} & a_{12}\\ a_{21}& a_{22} \end{matrix} \right]\\ B& = \left[ \begin{matrix} b_{11} & b_{12}\\ b_{21}& b_{22} \end{matrix} \right] \end{aligned}$

那么

$\begin{aligned} AB& = \left[ \begin{matrix} a_{11} & a_{12}\\ a_{21}& a_{22} \end{matrix} \right]\left[ \begin{matrix} b_{11} & b_{12}\\ b_{21}& b_{22} \end{matrix} \right]\\ & = \left[ \begin{matrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22}\\ a_{21}b_{11}+a_{22}b_{21}& a_{21}b_{12}+a_{22}b_{22} \end{matrix} \right] \end{aligned}$

显然一共需要$8$次乘法和$4$次加法。

(b)

利用快速幂的思想：

$X^n=\begin{cases} (X^{n/2})^2 & n=2k,k\in \mathbb N\\ (X^{(n - 1)/2})^2 X & n=2k+1,k\in \mathbb N \end{cases}$

所以时间复杂度为：

$\begin{aligned} T(n)&= T\left(\frac n 2\right) +\Theta(c)\\ T(n)&\in \Theta(\log n) \end{aligned}$

(c)

记

$\begin{aligned} X^n = \left[ \begin{matrix} a_n & b_n\\ c_n& d_n \end{matrix} \right] \end{aligned}$

记$l_n$为$X^n$中元素的最大二进制位数，那么由

$\begin{aligned} X^{n+1}&= \left[ \begin{matrix} a_{n+1} & b_{n+1}\\ c_{n+1}& d_{n+1} \end{matrix} \right]\\ &= \left[ \begin{matrix} a_n & b_n\\ c_n& d_n \end{matrix} \right]\left[ \begin{matrix} 0 & 1\\ 1& 1 \end{matrix} \right]\\ &= \left[ \begin{matrix} b_n & a_n+b_n\\ d_n& c_n+d_n \end{matrix} \right] \end{aligned}$

可以推出（加法最多让位数加$1$）

$l_{n-1}\le l_n \le l_{n-1} + 1$

所以

$l_n \in O(n)$

(d)

将(b)中的递推关系修改为

$\begin{aligned} T(n)&= T\left(\frac n 2\right) +M(n) \end{aligned}$

迭代的轮数为$\Theta(\log n)$，每轮的时间复杂度为$M(n)$，所以总时间复杂度小于等于

$O(M(n)\log n)$

(e)

对递推式

$\begin{aligned} T(n)&= T\left(\frac n 2\right) +M(n) \end{aligned}$

利用递归树进行分析，在第$i$层中，一共有$1$个节点，节点的大小为$\frac n {2^i}$，对应的时间复杂度为$M\left(\frac n {2^i}\right)= \Theta \left(\frac {n^{\alpha}} {(2^\alpha)^i}\right)$，所以总时间复杂度为

$\begin{aligned} \Theta\left(\sum_{i=1}^{\log n}\frac {n^{\alpha}} {(2^\alpha)^i} \right) &=\Theta\left(n^{\alpha}\sum_{i=1}^{\log n}\frac {1} {(2^\alpha)^i} \right)\\ &= \Theta\left(n^{\alpha} \right) \end{aligned}$

小结

该算法最终的时间复杂度和大整数乘法的时间复杂度相当。

回顾fib2算法：

$f$为长度为$n+1$的数组
$f[0]=0,f[1]=1$
for $i=2,\ldots, n$:
- $f[i]=f[i-1]+f[i-2]$
return $f[n]$

该循环有$i$轮，由之前的讨论可得，$f[i]$的比特数为$O(n)$，由加法的时间复杂度可得，第$i$轮的时间复杂度为$O(n)$，所以总时间复杂度为$O(n^2)$。于是最终的问题就是比较乘法的时间复杂度是否可以小于$O(n^2)$。

关于备注的说明：

记

$\begin{aligned} \lambda_1 &=\frac{1+\sqrt{5}}{2}\\ \lambda_2 &=\frac{1-\sqrt{5}}{2}\\ \Lambda &=\text{diag}(\lambda_1,\lambda_2) \end{aligned}$

实际上，$\alpha_1,\alpha_2$是$X$的特征值，并且由于$X$是对称矩阵，所以存在可逆矩阵$P$，使得

$X=P^{-1}\Lambda P$

从而

$\begin{aligned} X^n&= P^{-1}\text{diag}(\lambda_1^n,\lambda_2^n) P \end{aligned}$

所以该算法实际上给出了计算无理数$n$次幂的间接方法。