分治策略

对分治策略的分析见文章[递归分析]http://aisakaki.com/?p=406

1、分解(分)

2、解决(治)

3、合并

一些使用分治策略的算法

①归并排序

T(n)=2T(n/2)+Θ(n)

2为子问题数目,n/2为子问题规模,Θ(n)为附加计算量(分治法运行时间)

通过主定理case2,可以得到其T(n)=O(nlgn)

②二分查找

分:二分

治:比较。只在一个子数组中递归

T(n)=1*T(n/2)+Θ(1)

1个子问题

③乘方问题

求x^n

如果用朴素方法,那么T(n)=O(n)

如果采用分治策略,那么T(n)=T(n/2)+Θ(1)=O(lgn) (master method) <O(n)

*注意奇偶n的处理,但其递归式不变

只有一个子问题,画递归树的话就是一条链

④非不拉几数列

Fn=Fn-1 + Fn-2 if n>=2

Fn=0 if n=0

Fn=1 if n=1

1*若采用朴素的递归方式,不停计算Fn-1,Fn-2,触底就返回,那么

T(n)=Ω(φ^n) φ=(1+√5)/2 (φ为黄金比例,神奇)

子问题的规模仅仅缩小到了n-1,递归树非常庞大

复杂度为指数级,代价很高,所以此种方法不好。

最理想的算法复杂度为多项式级

2*事实上,在建立非不拉几递归树的时候,会发现很多公共子树,这些子树重复计算,产生了大量冗余。

如果考虑从底向上计算(线性。依次计算F(1),F(2),F(3),….),那么其复杂度会是O(n)

3*有一个更简单的办法(数学),F(n)=φ^n/√5并取整至最接近的整数,复杂度即为③中的问题,为O(lgn)

由于φ为浮点数,所以这样不精确且对运算要求极高,在现有机器上无法运行

4*第二种数学方法

Fn-1 Fn = 1 1 ^n

Fn Fn-2 = 1 0

(左右皆为矩阵,右边是矩阵的n次幂,待安装数学公式插件再修改)

证明:数学归纳法。比较简单,证略。

其复杂度为O(lgn)

⑤矩阵乘法

朴素方法:三层循环,i对应左行,j对应右列,k对应遍历每个元素。T(n)=O(n^3)

分治方法1:

利用分块矩阵,将母矩阵变成2*2的矩阵

A= A11 A12

A21 A22

B=B11 B12

B21 B22

C=C11 C12

C21 C22

由此可以写得四个表达式

c11=A11B11 + A12B21

C12=A11B12+A12B22

C21=A21B11+A22B22

C22=A21B12+A22B22

由此可得每次递归需要将有八个递归子问题(乘),并加上4次矩阵加法时间

(8个规模为n/2的矩阵乘法(递归)和4个规模为n/2(即合并起来为一个规模为n)的矩阵加法(非递归,常数)

所以其递归表达式为 T(n)=8T(n/2)+Θ(n^2)

由主定理得,T(n)=Θ(n^3)

此方法效率依然很低,和朴素方法没什么区别。

思考:为什么效率低?

因为矩阵乘法是Θ(n^3)级复杂度,而一次递归将产生8个子问题,每个子问题皆矩阵乘法

而矩阵加法是Θ(n^2)级复杂度。所以为了使递归树变小,我们应尽量减少矩阵乘法,多做矩阵加法。

比如,一次递归产生8个子矩阵乘法问题,递归树太“茂盛”了,我们能否减小到7个?

通过这种思考下去,就想到了第二种方法

分治方法2:Strassen方法

该算法具体内容见https://blog.csdn.net/qwertyuer/article/details/44255087

该算法下,T(n)=7T(n/2)+Θ(n^2)=Θ(n^lg7)<Θ(n^3)

分:将AB 矩阵分为8个子矩阵

治:中间计算过程

合:将子问题的解合并为原问题的解

未完待续

  • 本文作者: aisaka
  • 本文链接: 444.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!