我知道该算法使用时间复杂度的 8 次乘法和 4 次加法：
乘法是在每个n/2 * n/2矩阵上完成的。我对此有几个问题：
n * n矩阵是否最终通过执行减小到n=1大小T(n/2)？如果这样返回a11*b11似乎没有意义，就像1*6为a11*b11下面的矩阵返回：
然后基本情况应该n==2执行 else 部分，因为下面的操作似乎是合法的。
0(n^2)？我的意思是，我们完全不处理矩阵加法，而只是处理数字，因为每个矩阵都简化为2 * 2如下所示：
所以加法部分应该只贡献4？（为什么0(n^2)？）
如果我正确理解了这个问题，那么部分可以回答如下。
事实上，所有矩阵最终都归结为1*1矩阵；这应该不足为奇，因为矩阵乘法的基本定义最终是根据底层环的乘法来定义的。
加法部分在递归的每个级别上都具有复杂性0(n^2)，因为加法是在乘法的递归评估结果上执行的。
1) 矩阵最终会缩减为 1*1 矩阵。但没关系，你甚至可以为 n==2 设置一个基本情况，它仍然是 O(1) 时间，因为乘以 2*2 矩阵仍然需要恒定的时间，并且复杂度仍然保持不变。
2）加法部分应该具有复杂度 O(n^2)，因为每个子问题都有 (n^2)/4 个元素，并且有 4 个这样的子问题，这意味着您实际上正在执行 n^2 操作，结果为 O(n^2 ) 复杂性。
只是看到算法可能不清楚为什么加法步骤需要 theta(n^2) 时间。我也有同样的困惑，即加法应该花费恒定的时间。addMatrices() 方法中使用 2*2 矩阵，如果我们进行以下更改
C[rowC][columnC] = A[0][0] + B[0][0];
然后它也给出相同的结果。
但是，一旦我们采用 4*4 矩阵，就会看到调用堆栈中会发生一些 addMatrices() 方法调用，这会从矩阵 A 和 B 中添加多个元素。这就是为什么需要在循环内运行加法。
实施该程序后，它更容易理解。我已经尝试解释了，详细请参考方法注释。
package matrix;
/***
* Square Matrix multiplication(2^x) using divide and conquer technique
*
* @author kmandal
*
*/
public class MatrixMultiplication {
public static void main(String[] args) {
int[][] A = { { 1, 2 }, { 3, 4 } };
int[][] B = { { 5, 6 }, { 7, 8 } };
int C[][] = squareMatrixMultiplyRecursive(A, B);
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < C.length; j++) {
System.out.print(C[i][j] + " ");
}
System.out.println();
}
}
private static int[][] squareMatrixMultiplyRecursive(int[][] A, int[][] B) {
return squareMatrixMultiplicationDNC(A, B, 0, 0, 0, 0, A.length);
}
/**
* <pre>
* Let A and B are 2 square matrices with dimension 2^x
* A = [
* A00 A01
* A10 A11
* ]
* ,
* B = [
* B00 B01
* B10 B11
* ]
*
* C be another matrix stores the result of multiplication of A and B.
*
* C = A.B;
*
* C = [
* C00 C01
* C10 C11
* ]
*
* where
* for C00 calculation, elements in 0th row of A and 0th column of B considered
* C00 = A00*B00+A01*B10;
*
* for C01 calculation, elements in 0th row of A and 1st column of B considered
* C01 = A00*B01+A01*B11;
*
* for C10 calculation, elements in 1st row of A and 0th column of B considered
* C10 = A10*B00+A11*B10;
*
* for C11 calculation, elements in 1st row of A and 1st column of B considered
* C11 = A10*B01+A11*B11;
*
* Here we are using index based calculation,
* hence time complexity for index calculation is Theta(1).
*
* We have divided the problem into 8 sub-problems with size n/2.
* Hence the recurrence for this divide part is: 8T(n/2).
*
* Additionally we need to consider the cost of matrix addition step,
* which is Theta(n^2). For more details refer addMatrices() method.
*
* Hence the recurrence relation become
* T(n) = Theta(1) + 8T(n/2)+ Theta(n^2);
*
* Applying Master theorem,
* the time complexity of this algorithm become O(n^3)
* </pre>
*
* @param A
* @param B
* @param rowA
* @param columnA
* @param rowB
* @param columnB
* @param size
* @return
*/
private static int[][] squareMatrixMultiplicationDNC(int[][] A, int[][] B,
int rowA, int columnA, int rowB, int columnB, int size) {
int[][] C = new int[size][size];
if (size == 1) {
C[0][0] = A[rowA][columnA] * B[rowB][columnB];
} else {
int newSize = size / 2;
// calculate C00 = A00*B00+A01*B10;
addMatrices(
C,
squareMatrixMultiplicationDNC(A, B, rowA, columnA, rowB,
columnB, newSize),
squareMatrixMultiplicationDNC(A, B, rowA,
columnA + newSize, rowB + newSize, columnB, newSize),
0, 0);
// calculate C01 = A00*B01+A01*B11;
addMatrices(
C,
squareMatrixMultiplicationDNC(A, B, rowA, columnA, rowB,
columnB + newSize, newSize),
squareMatrixMultiplicationDNC(A, B, rowA,
columnA + newSize, rowB + newSize, columnB
+ newSize, newSize), 0, newSize);
// calculate C10 = A10*B00+A11*B10;
addMatrices(
C,
squareMatrixMultiplicationDNC(A, B, rowA + newSize,
columnA, rowB, columnB, newSize),
squareMatrixMultiplicationDNC(A, B, rowA + newSize, columnA
+ newSize, rowB + newSize, columnB, newSize),
newSize, 0);
// calculate C11 = A10*B01+A11*B11;
addMatrices(
C,
squareMatrixMultiplicationDNC(A, B, rowA + newSize,
columnA, rowB, columnB + newSize, newSize),
squareMatrixMultiplicationDNC(A, B, rowA + newSize, columnA
+ newSize, rowB + newSize, columnB + newSize,
newSize), newSize, newSize);
}
return C;
}
/**
* Matrix I represented by 2 dimensional array hence for addition of 2
* matrices, need to fetch same element from both the matrices and then
* add them. Traversing 2D array mean need to access elements by row and
* column index thus need to loop inside loop. Hence time complexity of
* addition is Theta(n^2)
*
* @param C
* @param A
* @param B
* @param rowC
* @param columnC
*/
private static void addMatrices(int[][] C, int[][] A, int[][] B, int rowC,
int columnC) {
int n = A.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i + rowC][j + columnC] = A[i][j] + B[i][j];
}
}
}
}
Output:
19 22
43 50