题解 | #矩阵乘法#

矩阵乘法

http://www.nowcoder.com/practice/bf358c3ac73e491585943bac94e309b0

描述

给定两个 nn的矩阵 A和 B，求 AB 。
数据范围：

$1 \le n \le 500$
$-100 \le n \le 100$

方法一

思路

模拟计算
矩阵乘法的规则为:假设矩阵A与矩阵B相乘（默认满足乘法条件），矩阵C为结果，则其满足如下公式：
故要求矩阵C，只需模拟上述公式的过程，求出每一个位置的值即可。

具体步骤

1.首先calculate函数是用于计算指定位置的值的；
2.循环遍历矩阵C的每一个位置，使用calculate计算该位置的值；
3.遍历完成，C矩阵也就出来了。

代码如下：

import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 
* @param a int整型二维数组 第一个矩阵
* @param b int整型二维数组 第二个矩阵
* @return int整型二维数组
*/
public int[][] solve (int[][] a, int[][] b) {
   //矩阵相乘后的行数等于第一个矩阵的行数，列数等于第二个矩阵的列数
    int[][] res =new int[a.length][b[0].length];
   for(int i = 0;i < a.length;++i){
       for(int j = 0;j < a.length;++j){
           int sum = 0;
           for(int k = 0;k < a.length;++k){
              sum += a[i][k] * b[k][j];
           }
           res[i][j] = sum;
       }
   }
   return res;
}
}

时间复杂度： $O(n^3)$ ，calculate一重循环，主函数中双重循环，所以是 $O(n^3)$ ；
空间复杂度： $O(n^2)$ ，res矩阵所需空间为 $O(n^2)$ 。

方法二

思路

缓存优化
一个编写良好的计算机程序常常具有良好的局部性，也就是它们倾向于应用邻近于其它最近引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性被称为局部性原理。
局部性分为空间局部性和时间局部性，而有良好局部性的程序比局部性差的程序运行得更快，在一个具有良好的空间局部性的程序中，如果一个内存位置被引用了，那么程序很可能在不久的未来引用附近的一个内存位置。
而像本题中用于存储矩阵的二维数组，其在空间中实际上是顺序存储的，而方法一种对于矩阵数据的读取实际上是跳着读取的，其并不具备良好的空间局部性。
故可以通过顺序读取矩阵中的数据来进行矩阵乘法，从而提高程序的空间局部性，来提高算法的速度。
对局部性这些问题感兴趣的可以看看CSAPP这本书。
具体步骤

代码如下：

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 
   * @param a int整型二维数组 第一个矩阵
   * @param b int整型二维数组 第二个矩阵
   * @return int整型二维数组
   */
  public int[][] solve (int[][] a, int[][] b) {
      //矩阵相乘后的行数等于第一个矩阵的行数，列数等于第二个矩阵的列数
       int[][] res =new int[a.length][b[0].length];
      for(int i = 0;i < a.length;++i){
          for(int j = 0;j < a.length;++j){
              // 优先访问
              int temp = a[i][j];
              for(int k = 0;k < a.length;++k){
                 // 行*列相加
                 res[i][k] += temp * b[j][k];
              }
          }
      }
      return res;
  }
}

时间复杂度： $O(n^3)$ ，三重循环；
空间复杂度： $O(n^2)$ ，结果矩阵需要 $O(n^2)$ 的空间。
方法一和方法二的时间复杂度为 $O(n^3)$ ，是比较大的，那么有没有更优的算法来实现矩阵乘法呢？
当然是有的，1969年，Volker Strassen提出了第一个算法时间复杂度低于 $O(n^3)$ 的矩阵乘法算法，算法复杂度约为 $O(n^2.807)$ 。但是Strassen算法只有在对于维数比较大的矩阵,性能上才有很大的优势，可以减少很多乘法计算。Strassen算法证明了矩阵乘法存在时间复杂度低于 $O(n^3)$ 的算法的存在，后续学者不断研究发现新的更快的算法，截止目前时间复杂度最低的矩阵乘法算法是Coppersmith-Winograd方法的一种扩展方法.
Strassen算法笔者就不具体介绍了，感兴趣的可以自己百度，下面就来实现这个算法吧。
当然也可以通过使用多线程来进行矩阵乘法的运算，从而降低算法的运行时间。