Сумма подматриц большей матрицы
У меня есть большая матрица на входе, и у меня есть размер меньшей матрицы. Я должен вычислить сумму всех возможных меньших матриц, которые могут быть сформированы из большей матрицы.
Пример.
Размер входной матрицы: 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;
}
Я думаю, это слишком медленно, кто-нибудь может предложить более быстрый путь?
Решение
Ваш текущий алгоритм O ((m — p) * (n — q) * p * q). Наихудший случай — когда p = m / 2 и q = n / 2.
Алгоритм, который я собираюсь описать, будет O (m * n + p * q), который будет O (m * n) независимо от p и q.
Алгоритм состоит из 2 шагов.
Пусть размер входной матрицы А будет 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 (m * n), используя это отношение для вычисления каждого элемента в O (1):
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], который является всей подматрицей, которую мы вычисляем, кроме текущей строки, был вычислен ранее. Вы сохраняете сумму префикса текущей строки, чтобы вы могли использовать ее для быстрого вычисления суммы текущей строки.
Это еще один способ вычислить B[i, j] в O (1), используя свойство суммы префикса 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
Затем вторым шагом является вычисление матрицы результатов 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]
Следовательно, сложность второго шага будет O (p * q).
Окончательная сложность, как указано выше, O (m * n), так как p <= м и д <= п.
Другие решения
Других решений пока нет …