java - 如何找到矩阵中所有子平方的总和？

Question

我正在寻找一个非常大的矩阵的所有子平方的总和，其中

{ {1, 2}{3,4} } 在二维矩阵中会返回 20。我已经使用 java 实现了这个，但是程序非常慢。是否有更快的方法或其他更快的语言？

public class insaneMat
{
public static void main(String[] args)
{
    int[][] mat = new int[10000][10000];

    try
    {
        Scanner input = new Scanner (new File("file.in"));  
        int count = 0;
        for (int r = 0; r < mat.length; r++)
        {
            for (int c = 0; c <mat[r].length; c++)
            {
                mat[r][c] = input.nextInt();
                count++;
                System.out.println("Loaded num " + count);
            }
        }
    }
    catch(Exception e)
    {
        System.out.println("ERROR!");
    }

    int n = mat.length;
    int k;
    int sum = 0;
    for (k = 1; k < 10000; k++)
    {
        System.out.println("Calculating with subsquare of size " + k);
        for (int i=0; i<n-k+1; i++)
        {
            for (int j=0; j<n-k+1; j++)
            {
                for (int p=i; p<k+i; p++)
                    for (int q=j; q<k+j; q++)
                        sum += mat[p][q];
            }
        }
    }
    System.out.println("Number = " + sum);

}   

这在 java 中按预期工作，除了它非常非常慢。如上所述，该程序适用于 2x2 矩阵，但每小时运行大约 30 个子方 block 。无论我使用 Java 还是其他语言，都可以用更快的方法完成吗？ Matlab 有用吗？

Answer 1

解决这个问题的方法是分析每个元素 [i,j] 属于大小为 N 的矩阵的多少个子方...调用此函数 C(n, i ,j).然后计算所有 i, j 的 C(n, i, j) * element[i, j] 的总和。

计算的复杂度将是 O(N^2) ... 与您当前算法的 O(N^5) 相比(而且我怀疑算法可能是错误的...如果您想要从 1 到 N-1 的所有子方...并且真正的复杂度是 O(N!)。)

无论如何，您只需要一点数学知识 :-)

---

警告，这些金额将变得非常大。