首页  |  Linux  |  C/C++  |  网络编程  |  Python   |  Algorithm  |  数据库  |  经验  |   人生 & 随想   |  站内搜索  |  关于

<<< previous

该文已被浏览1692

O(1)时间内求解子矩阵的和

2016-02-03

给出一个3X4的矩阵,如下:
1  2  3  4
5  6  7  8
9  10 11 12
要求解一个以(0,0)为左上角,以(i,j)为右下角的子矩阵的和.例如输入i = 2, j = 2 时,所求的子矩阵为:
1  2  3
5  6  7
9  10 11
这个子矩阵的的和为54,因此输出54.
   最容易想到的方法是根据输入的 ij 的值,确定出子矩阵,之后用两个 for 循环来遍历这个子矩阵,将子矩阵中的元素相加,从而得出子矩阵的和。这种方法的时间复杂度是 O(mxn), 其中 m,n 分别为子矩阵的行数和列数.
   如何在 O(1) 时间内求得子矩阵的和呢?这就需要耗费一定的额外空间。正如鱼和熊掌不可兼得一样,时间和空间的关系亦是如此,想要速度快一些,就必须多耗费一些空间。这里就要多用一个与给定矩阵大小相同的辅助空间 auxility[3][4],然后通过一定的算法,在这个辅助空间中存储子矩阵的和,使得 auxility[m][n] 表示以(0,0)为左上角,以(m,n)为右上角的子矩阵的和。这样的预备工作完成以后,就可以在 O(1) 时间内求得给定子矩阵的和。
下面来介绍在辅助空间内存储子矩阵的和的算法:
  1. 将给定矩阵 matrix[M][N] 的第一行复制到辅助空间 auxility[M][N]中.
  2. 在矩阵列方向上计算和并将结果保存到辅助空间 auxility[][] 中.
  3. 在辅助空间行方向上计算和并更新辅助空间 auxility[][].
用文字表述算法可能有些不清楚,下面使用具体的C++代码来表示上述算法:
#define M 3
#define N 4
void calSubmatrixSum(int matrix[M][N], int auxility[M][N])
{
    // 将矩阵的第一行复制到辅助空间中
    for(int i = 0; i < N; ++i)
        auxility[0][i] = matrix[0][i];
    // 在矩阵的列方向上计算和
    for(int i = 1; i < M; ++i)
        for(int j = 0; j < N; ++j)
            auxility[i][j] = auxility[i-1][j] + matrix[i][j];
    // 在辅助空间的行方向上计算和
    for(int i = 0; i < M; ++i)
        for(int j = 1; j < N; ++j)
            auxility[i][j] += auxility[i][j-1];
}
之后要求解以(0,0)为左上角,以(i,j)为右下角的子矩阵的和,只要输出 auxility[i][j] 的值即可.
使用这种方法计算子矩阵的和的复杂度如下:
时间复杂度: O(1)        
空间复杂度: O(mxn)    


一如既往,如果你对文章中的内容有任何疑问,或者是发现文章中有任何错误,都可以通过下面的地址发邮件告诉我.
E-mail: rytubuntulinux@gmail.com