11

正如其他帖子中指出的那样，NxN可以使用 2-d kadane 算法及时找到矩阵中的最大和子矩形。O(n^3)但是，如果矩阵是稀疏的，特别是O(n)非零条目，O(n^3)时间可以被打败吗？

如果它有帮助，对于我感兴趣的当前应用程序，有一个解决方案就足够了，该解决方案在矩阵的每一行和每一列中最多假设一个非零值。然而，在我未来的应用程序中，这个假设可能不合适（只是稀疏性会成立），无论如何我的数学直觉是，可能有很好的解决方案可以简单地利用稀疏性而不进一步利用矩阵是对角线和置换矩阵的乘积。

4

1 回答 1

10

是的，它可以做得更好。

首先，让我们考虑一个数据结构，它允许我们

  1. O(logn)及时 更新底层一维数组的任何单个值
  2. O(1)及时求出数组的最大子数组之和

实际上，如下所示的平衡二叉树可以完成这项工作。树形结构可以描述为：

  1. 树的每个叶节点代表数组的每个元素。
  2. 如果内部节点覆盖范围[a, b]，则其左子节点覆盖范围，其右子节点覆盖[a, c]范围[c + 1, b]，其中c = floor((a + b) / 2)).

  3. 根节点覆盖 range [1, n]。

                          O
                    /   \
                  /       \
                /           \
              /               \
            /                   \
          O                       O
        /   \                   /   \
       /     \                 /     \
      /       \               /       \
    O           O           O           O
   / \         / \         / \         / \
 o     o     o     o     o     o     o     o
A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]  A[8]

v每个节点（包括叶节点和内部节点） 都有 4 个字段：

  • S[v]v:范围内 所有值的总和
  • M[v]v:范围内 的最大子数组和
  • L[v]v: 从' 范围 左侧开始的最大子数组的总和
  • R[v]v: 在' 范围 右侧结束的最大子数组的总和

根据以上定义，我们可以发现以下更新规则：

  • 对于任何叶节点v, S[v] = A[v],M[v] = L[v] = R[v] = max{0, A[v]}
  • 对于任何内部节点v及其子节点l和r，
    • S[v] = S[l] + S[r]
    • M[v] = max{M[l], M[r], R[l] + L[r]}
    • L[v] = max{L[l], L[r] + S[l]}
    • R[v] = max{R[r], R[l] + S[r]}

最后，我们就可以实现开头提到的操作了。

  • 要更新A[i]，我们可能会在树中找到相应的叶节点，并使用上述规则将沿其路径的字段更新到根。
  • 最大子数组和是简单的M[root]。

现在让我们讨论如何使用这个数据结构找到最大矩形。如果我们将矩形的上一行和下一行固定为第 th 行i和j第 th 行，问题就变成了 1D 最大子数组和问题，其中A[k] = sum{B[i..j, k]}. 关键的见解是，对于一个固定的i，如果我们j按升序枚举，我们可以使用上面的数据结构来维护底层的一维数组并很​​快找到答案。伪代码描述了这个想法：

result = 0
for i in (1, 2, ..., n)
    set all fields of the binary tree T to 0
    for j in (i, i + 1, ..., n)
        for any k where B[j, k] != 0
            T.update(k, A[k] + B[j, k])
        result = max{M[root], result}
return result

假设矩阵包含m非零元素，该算法的时间复杂度为O(mn logn)。在您的情况下m = O(n)，时间复杂度是O(n^2 logn)并且优于O(n^3).

于 2013-07-11T13:57:18.627 回答