本课的主讲是Erik,讲了算法设计中特别重要的思想之一:分治法。好好体会这一课的精华。由于本人英文水平太差,这一课前前后后加起来的时间差不多一天。最后的VLSI问题还是没有听的太明白?求什么?
分治法将会用到很多的递归技术,分治法的分割基本步骤:
1:分--减小问题规模
2:治--处理问题
3:合并--这一步不是必须的,比如说,二分查找法就没有合并这一步
举例说明:
1.合并排序
2.二分查找
3.数的幂乘
直接的解法就是将X乘上n次,需要Theta(n)。我们可以使用分治的思想,将n个X的乘法分成2个X^(n/2)的子问题,并递归的求出X^(n/2)。
递归式为T(n) = T(n/2) + Theta(1)。用主方法可以解得T(n) = Theta(lgn)。何为主方法?第二讲有讲。必须记忆。
4.Fibonacci数列
最简单的方法就是递归解决,时间复杂度指数级别,BAD。
把式子展开成二叉树,观察不难发现,很多F_i我们重复计算了好些次,如果采用自低向上的方法来计算出每一个F_i,一直到F_n,这可以在线性时间内解决问题。这事典型的空间换时间做法,值得。
或者可以有另一种想法,我们可以利用斐波纳契数的一个性质,公式也不大出来了,和黄金分割点有关那个性质。不过,这玩意,你真得需要好好考虑数值稳定性的问题了。
还有办法可以进一步减小时间复杂度。Theta(lg n)!!!不过这需要了解一些Fibonacci数列的性质,[(Fn+1,Fn),(Fn,Fn-1)]=[(1,1),(1,0)]的n次方。这个式子可以用归纳法证明。前面数的幂乘的方法可以推广到矩阵的幂乘上,每一步的操作仍然是Theta(1),不再赘述。
5.矩阵乘(28章)
还记得以前学习C语言时候写的完全根据线性代数书上来的方法,还一阵陶醉。这的复杂度,这需要Theta(n^3)的时间。如果我们使用分治法来设计算法,最直观的想法是将矩阵划成块,需要8个矩阵乘和4个矩阵加法,8个矩阵乘用递归来解,时间复杂度Theta(n^3)。呵呵,命运呀。
隆重推出,Strassen算法,书上有详细证明。使用1+1=2做计算时候,从来不想着如何去证明1+1=2,使用这些算法的时候呀,也该不要想那么多,用上就是了。
最后一个分治法的例子,是关于VLSI的,说实话,我还是没有太明白这个例子的背景,虽然明白他的分析,但是:在干吗?了然的同学希望留个言指点一下,谢谢。
分享到:
相关推荐
第六章基本算法设计策略——分治法.pptx
主要是算法的课程设计,对分治法进行详细的分析和讲解,同时用java语言对其进行实现
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法
java实现strassen算法 运用了分治法和strassen原理 课堂作业
贪心算法和动态规划以及分治法的区别? (1) 贪心算法和动态规划.pdf
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。
算法设计 蛮力法 分治法 动态规划 贪心算法 分支限界法 回溯法 近似算法 减制法
关于分治法的算法结课论文,讲述了分治法与递归的联系与区别。分治法是解题思路,而递归是实现的方法,可用递归,也可用非递归
本资源为山东科技大学计算机算法设计与分析的实验报告,实现分治法求解棋盘问题算法,分析算法的复杂性。资料包含源码和实验报告,仅供参考,请勿抄袭! 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的...
算法设计与分析课内实验——分治法求众数。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
算法思想——递归与分治 算法思想——递归与分治
问题:对于平面上给定的N个点,给出所有点对的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。
用递推算法 迭代算法 公式法计算求第N个Fibonacci数,计算机能算出最大Fibonacci时N的值,计算1分钟内能计算几个Fibonacci,用公式法计算Fibonacci,当出现错误时,N为多少。
学习常用算法之(6)分治法
算法分析PPT(分治法-大整数、矩阵相乘).ppt)
算法分析第二单元员 分治法的学习 中的经典问题3 也叫做归并排序
【C++】斐波那契数列应用的一个实例。这是关于斐波那契数列的一个例子,用C++语言实现
Strassen是采用分治算法的思想,将所给矩阵分成2阶矩阵 分治的方法循序渐进处理各个小矩阵的相乘,一个矩阵可以分成更多小的矩阵的。