书籍介绍:

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)

那么

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

(b)

利用快速幂的思想:

所以时间复杂度为:

(c)

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

可以推出(加法最多让位数加$1$)

所以

(d)

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

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

(e)

对递推式

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

小结

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

回顾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)$。

关于备注的说明:

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

从而

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