x*********w
发帖数: 533 | 1 矩阵乘法，维度不一定是2的power, divided and conquer
C1 C2 A1 A2 B1 B2
= *
C3 C4 A3 A4 B3 B4
C1 = A1*B1 + A2*B3
C2 = A1*B2 + A2*B4
.........
inplace的程序感觉蛮tricky的：
===========================================
public class StrassenMatrixAlgo {
static void _inner_mul(int[][] a, int ra, int ca, int[][] b, int rb, int cb
,
int[][] c, int rc, int cc, int dim, int orgDim)
{
if (rc >= orgDim || cc >= orgDim ||
ra >= orgDim || ca >= orgDim ||
rb >= orgDim || cb >= orgDim)
return;
if (dim <= 1)
{
c[rc][cc] += a[ra][ca] * b[rb][cb];
return;
}
//c1
_inner_mul(a, ra, ca, b, rb, cb, c, rc, cc, dim/2, orgDim);
_inner_mul(a, ra, ca + dim/2, b, rb + dim/2, cb, c, rc, cc, dim/2, orgDim);
//c2
_inner_mul(a, ra, ca, b, rb, cb + dim/2, c, rc, cc + dim/2, dim/2, orgDim);
_inner_mul(a, ra, ca + dim/2, b, rb + dim/2, cb + dim/2, c, rc, cc + dim/2
, dim/2, orgDim);
//c3
_inner_mul(a, ra + dim/2, ca, b, rb, cb, c, rc + dim/2, cc, dim/2, orgDim);
_inner_mul(a, ra + dim/2, ca + dim/2, b, rb + dim/2, cb, c, rc + dim/2, cc
, dim/2, orgDim);
//c4
_inner_mul(a, ra + dim/2, ca, b, rb, cb + dim/2, c, rc + dim/2, cc + dim/2
, dim/2, orgDim);
_inner_mul(a, ra + dim/2, ca + dim/2, b, rb + dim/2, cb + dim/2, c, rc +
dim/2, cc + dim/2, dim/2, orgDim);
}
static int[][] MatrixMultiple(int[][] a, int[][] b)
{
int dim = a.length;
int[][] c = new int[dim][dim];
int d = 1;
while (d < a.length)
d *= 2;
_inner_mul(a, 0, 0, b, 0, 0, c, 0, 0, d, dim);
return c;
}
public static void main(String[] strs)
{
int[][] a = {{1,0,2}, {2,1,1}, {1,3,2}};
int[][] b = {{0,1,0}, {1,1,2}, {2,0,1}};
int[][] c = MatrixMultiple(a, b);
}
} | l*********8
发帖数: 4642 | 2 你这个不是inplace的吧？ 也不太可能in-place吧？
这个算法时间复杂度多少？ 我感觉是O(n^3) (假如A和B都是n by n的方阵)。 这样的
话，跟直接计算比，也没有优势了？
【在 x*********w 的大作中提到】
: 矩阵乘法，维度不一定是2的power, divided and conquer
: C1 C2 A1 A2 B1 B2
: = *
: C3 C4 A3 A4 B3 B4
: C1 = A1*B1 + A2*B3
: C2 = A1*B2 + A2*B4
: .........
: inplace的程序感觉蛮tricky的：
: ===========================================
: public class StrassenMatrixAlgo {
| x*********w
发帖数: 533 | 3
是O(n^2)啊
T(n) = 8*T(n/2) + n^2
【在 l*********8 的大作中提到】
: 你这个不是inplace的吧？ 也不太可能in-place吧？
: 这个算法时间复杂度多少？ 我感觉是O(n^3) (假如A和B都是n by n的方阵)。 这样的
: 话，跟直接计算比，也没有优势了？
| l*********8
发帖数: 4642 | 4 这个是O(n^3)吧。
根据master theorem,
T(n) = O(n ^ log2(8) ) = O(n^3)
【在 x*********w 的大作中提到】
:
: 是O(n^2)啊
: T(n) = 8*T(n/2) + n^2
| x*********w
发帖数: 533 | 5
没错，是O(n^3)， 不过可以用在parallel上
其实是 T(n) = 8*T(n/2)
【在 l*********8 的大作中提到】
: 这个是O(n^3)吧。
: 根据master theorem,
: T(n) = O(n ^ log2(8) ) = O(n^3)
| l*********8
发帖数: 4642 | 6 T(n) = 8*T(n/2) + O(1)的话， T(n)还是O(n^3).
parallel的话，的确得分块计算。 谢谢分享！ | z*******o
发帖数: 4773 | |
|
