算法导论 练习题 4.2-6

时间:2022-09-09 18:01:13

1、将A=kn*n和B=n*kn分别拆成k个n*n矩阵:A11,A21......AK1和B11,B12......B1K

      A和B相乘得k*k的矩阵,(A11*B11,A11*B12......A11*B1K......AK1*B11,AK1*B12...AK1*B1K)

      对其中每个乘法应用Strassen算法,则渐进时间是K*K*n的2.81次方

2、采取相同做法,将A=kn*n和B=n*kn分别拆成k个n*n矩阵

      A和B相乘得一个矩阵X=A11*B11+A12*B21+...A1K*BK1

      这里面有K个乘法,对其中每个乘法应用Strassen算法,则渐进时间是K*n的2.81次方