2

入力として大きな行列があり、小さな行列のサイズがあります。大きな行列から形成できるすべての可能な小さな行列の合計を計算する必要があります。

例。入力行列サイズ: 4 × 4

マトリックス：

1 2 3 4
5 6 7 8
9 9 0 0
0 0 9 9

入力より小さい行列サイズ: 3 × 3 (必ずしも正方形である必要はありません)

より小さな行列が可能:

1 2 3
5 6 7
9 9 0

5 6 7
9 9 0
0 0 9

2 3 4
6 7 8
9 0 0

6 7 8
9 0 0
0 9 9

それらの合計、最終出力

14 18 22
29 22 15
18 18 18

これは私がしました：

int** matrix_sum(int **M, int n, int r, int c)
{
    int **res = new int*[r];
    for(int i=0 ; i<r ; i++) {
        res[i] = new int[c];
        memset(res[i], 0, sizeof(int)*c);
    }

    for(int i=0 ; i<=n-r ; i++)
    for(int j=0 ; j<=n-c ; j++)
    for(int k=i ; k<i+r ; k++)
    for(int l=j ; l<j+c ; l++)
    res[k-i][l-j] += M[k][l];

    return res;
}

これは遅すぎると思います。誰かがより速い方法を提案できますか?

4

1 に答える 1

3

現在のアルゴリズムは O((m - p) * (n - q) * p * q) です。最悪のケースは、p = m / 2 および q = n / 2 の場合です。

これから説明するアルゴリズムは O(m * n + p * q) で、p と q に関係なく O(m * n) になります。

アルゴリズムは 2 つのステップで構成されます。

入力行列 A のサイズm x nを 、ウィンドウ行列のサイズを とするp x q。

まず、入力行列と同じサイズの計算済み行列 B を作成します。事前計算された行列 B の各要素には、サブ行列のすべての要素の合計が含まれます。その左上の要素は元の行列の座標 (1, 1) にあり、右下の要素は次の座標と同じです。計算している要素。

B[i, j] = Sum[k = 1..i, l = 1..j]( A[k, l] ) for all 1 <= i <= m, 1 <= j <= n

これは、この関係を使用して O(1) の各要素を計算することにより、O(m * n) で実行できます。

B[i, j] = B[i - 1, j] + Sum[k = 1..j-1]( A[i, k] ) + A[j] for all 2 <= i <= m, 1 <= j <= n

B[i - 1, j]は、現在の行を除いて計算している部分行列のすべてであり、以前に計算されています。現在の行のプレフィックスの合計を保持して、それを使用して現在の行の合計をすばやく計算できるようにします。

これは、O(1) で計算する別の方法B[i, j]で、2D 接頭辞の合計のプロパティを使用します。

B[i, j] = B[i - 1, j] + B[i, j - 1] - B[i - 1, j - 1] + A[j] for all 1 <= i <= m, 1 <= j <= n and invalid entry = 0

次に、2 番目のステップは、サイズが の結果行列 S を計算することですp x q。観察すると、S[i, j] は行列サイズ (m - p + 1) * (n - q + 1) のすべての要素の合計であり、左上の座標は (i, j) であり、右下は (i + m - p + 1, j + n - q + 1) です。

事前計算された行列 B を使用して、O(1) の任意の部分行列の合計を計算できます。これを適用して、結果行列 S を計算します。

SubMatrixSum(top-left = (x1, y1), bottom-right = (x2, y2))
     = B[x2, y2] - B[x1 - 1, y2] - B[x2, y1 - 1] + B[x1 - 1, y1 - 1]

したがって、2 番目のステップの複雑さは O(p * q) になります。

p <= m および q <= n であるため、最終的な複雑さは前述のように O(m * n) になります。

于 2012-12-16T01:56:37.510 に答える