6 N6 N0 c4 C/ `( w* N为了得到更快的算法,需要简化矩阵分割和再组合这两个步骤。一种方案是使用S t r a s s e n方法得到7个小矩阵。这7个小矩阵为矩阵D, E, ., J,矩阵D到J可以通过7次矩阵乘法, 6次矩阵加法,和4次矩阵减法计算得出。前述的4个小矩阵可以由矩阵D到J通过6次矩阵加法和两次矩阵减法得出. & ~( P& z% M9 x4 i3 R" G0 e! M: g0 [
用上述方案来解决n= 2的矩阵乘法。将某矩阵A和B相乘得结果C,如下所示:% T9 @" }( B2 W. Y) |5 M6 v( S& D
8 ]( W% V( t) D$ G4 q! i根据以上结果可得:& \- C" q# Y) _4 k5 i/ l
3 ]# k3 }' J; ?( l7 p( i+ J; d
对于上面这个2×2的例子,使用分而治之算法需要7次乘法和1 8次加/减法运算。而直接使用公式(2 - 1),则需要8次乘法和7次加/减法。要想使分而治之算法更快一些,则一次乘法所花费的时间必须比11次加/减法的时间要长。 ; b1 h2 }" P8 Y7 b 5 ?" m6 e' W( k N0 O假定S t r a s s e n矩阵分割方案仅用于n≥8的矩阵乘法,而对于n<8的矩阵乘法则直接利用公式(2 - 1)进行计算。则n= 8时,8×8矩阵相乘需要7次4×4矩阵乘法和1 8次4×4矩阵加/减法。每次矩阵乘法需花费6 4m+ 4 8a次操作,每次矩阵加法或减法需花费1 6a次操作。因此总的操作次数为7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接计算方法,则需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接计算方法快,至少要求5 1 2-4 4 8次乘法的开销比6 2 4-4 4 8次加/减法的开销大。或者说一次乘法的开销应该大于近似2 . 7 5次加/减法的开销。# |# g. I* u8 e5 s: u% ^
1 L5 [0 k8 F, e+ d
假定n<1 6的矩阵是一个“小”问题,S t r a s s e n的分解方案仅仅用于n≥1 6的情况,对于n<1 6的矩阵相乘,直接利用公式( 2 - 1)。则当n= 1 6时使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。直接计算时需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的开销与一次加/减法的开销相同,则S t r a s s e n方法需要7 8 7 2次操作及用于问题分解的额外时间,而直接计算方法则需要7 9 3 6次操作加上程序中执行f o r循环以及其他语句所花费的时间。即使直接计算方法所需要的操作次数比St r a s s e n方法少,但由于直接计算方法需要更多的额外开销,因此它也不见得会比S t r a s s e n方法快。& e' R& N# B, i) Z2 u
9 \8 p5 d! @+ Q( I. l5 t& B
n 的值越大,Strassen 方法与直接计算方法所用的操作次数的差异就越大,因此对于足够大的n,Strassen 方法将更快。设t (n) 表示使用Strassen 分而治之方法所需的时间。因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于k(k至少为8,也许更大,具体值由计算机的性能决定). 用迭代方法计算,可得t(n) = (nl og27 )。因为l og27 ≈2 . 8 1,所以与直接计算方法的复杂性(n3 )相比,分而治之矩阵乘法算法有较大的改进。 + X5 R# m" D9 S' W0 A, u . M5 K! N2 M& d0 K* l注意事项6 q7 \* E9 a- i
& g) H. I# I& Z. w
分而治之方法很自然地导致了递归算法的使用。在许多例子里,这些递归算法在递归程序中得到了很好的运用。实际上,在许多情况下,所有为了得到一个非递归程序的企图都会导致采用一个模拟递归栈。不过在有些情况下,不使用这样的递归栈而采用一个非递归程序来完成分而治之算法也是可能的,并且在这种方式下,程序得到结果的速度会比递归方式更快。解决金块问题的分而治之算法(例2 - 2)和归并排序方法( 2 . 3节)就可以不利用递归而通过一个非递归程序来更快地完成。6 L( m- r" z4 a2 O+ O. O
6 ~0 Q, b5 s& j2 g& U7 o3) 对较轻的金块进行比较以确定哪一个金块最轻,对较重的金块进行比较以确定哪一个金块最重。对于节点A到C执行这种比较。: G9 I) m6 m) }
: ~, {: l6 d5 l# O) L; F
根据上述步骤,可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数,若n < 1,则程序返回f a l s e,否则返回t r u e。 5 N8 `6 L7 Y# r; F x2 m: T 6 ], c8 l. q* ~: j当n≥1时,程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量,w [ M a x ]为最大的重量。 4 ? O, w/ I: _' z8 B p& j/ W3 M' }- k. `' x/ U首先处理n≤1的情况。若n>1且为奇数,第一个重量w [ 0 ]将成为最小值和最大值的候选值,因此将有偶数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时,首先将两个重量值放在for 循环外进行比较,较小和较大的重量值分别置为Min和Max,因此也有偶数个重量值w[2:n-1]参与for循环。4 J- E4 G7 w1 w; Z' O
' L, b" H- m3 E在for 循环中,外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应,而内层的i f负责找出较小重量值和较大重量值中的最小值和 $ u) f+ v2 L8 z" g7 l) L# R7 ^0 ? , l, O* G8 i, Z( h+ S最大值,这个工作对应于3 )。for 循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较,根据比较结果来修改M i n和M a x(如果必要)。 Q" ?; y" h% y' J 8 ^7 E8 T. _! o2 {( m. t1 A9 r2 Z下面进行复杂性分析。注意到当n为偶数时,在for 循环外部将执行一次比较而在f o r循环内部执行3 ( n / 2 - 1 )次比较,比较的总次数为3 n / 2 - 2。当n 为奇数时,f o r循环外部没有执行比较,而内部执行了3(n-1)/2次比较。因此无论n 为奇数或偶数,当n>0时,比较的总次数为「3n/2ù-2次。# T* ~- J" q8 U& U3 N
; K3 i& ^8 f; E4 \# H程序14-1 找出最小值和最大值的非递归程序 ; P7 k( R, J0 V7 v# N: i D7 T ; t2 Y+ X7 ^+ Q- M N' Btemplate<CLASS T> 4 t; ^2 H C2 j1 k- b( [/ C! L H % ?) x: Z+ U" a% G6 G9 o' Vbool MinMax(T w[], int n, T& Min, T& Max)" v5 {+ q+ w7 B" s5 D6 b8 U; s9 [. t0 S