绝对矩阵之和

Question

这是之前 HackerEarth Challenge -

的一个问题

Roy 有一个大小为 NxN 的矩阵。行和列的编号从 0 到 N-1。第 i 行的第 j 列包含 i 和 j 之间的绝对差值。换句话说，Matrix[i][j] = abs(i-j) 其中 0 ≤ i，j < N。你的任务是找到这个矩阵的总和，即

sum = 0
for i=0 to N-1
    for j=0 to N-1
        sum += Matrix[i][j]

这是我对这个问题的解决方案 -

public static long getSum(int num, long acc) {
        if (num == 1)
            return acc;
        long sum = 0;
        for (int i = 0; i < num; i++) {
            sum += i;
        }
        sum = sum * 2;
        return getSum(num - 1, acc + sum);
    }

但是对于大于 4500 的大数字，此函数会失败。我收到 Stack Over Flow Error。在这里，我基本上尝试了两件事来保持代码优化 -

使用尾递归，并且
保持运行命令这个功能的时间'n'

所以请告诉我我是否正确地实现了这里的两件事。如果是，我还能做些什么来优化这段代码。感谢您的帮助。

Answer 1

尾递归

尾递归无法保护您免受 Java 中的堆栈溢出。其他一些语言可以识别 tail-calls 并在编译期间优化它们，因此它们不会扩展堆栈。

...tail call optimization is hard to do in the JVM because of the security model and the need to always have a stack trace available.

（来自 Does the JVM prevent tail call optimizations?）

然而，用循环替换尾递归很容易：

public static long getSum(int num, long acc) {
    while (num > 1) {
        long sum = 0;
        for (int i = 0; i < num; i++) {
            sum += i;
        }
        sum = sum * 2;
        //set up values for next loop
        num--;
        acc += sum;
    }
    return acc;
}

大O

keep running time of this function of order 'n'

你还没有做到这一点。可以清楚地看到 num 上有 2 个嵌套循环，并且 num 正在减少，我认为这使得它 O(n log n)

Answer 2

矩阵结构很简单（我只画了右上半部分，左下半部分一样，镜像）

0 1 2 3 4 5 ...
. 0 1 2 3 4 ...
. . 0 1 2 3 ...
. . . 0 1 2 ...
. . . . 0 1 ...
. . . . . 0 ...

很明显第K行是等差数列0..(N - K - 1)，所以和是

Sk = (N - K - 1) * (N - K) / 2

总和为（O(N) 解）

S = 2 * Sum[k = 0..N-1] (Sk)

此外，虽然每行的和是'triangular'个数，但三角数的和是'Tetrahedral number'，并且有一个封闭的公式，导致O（1）解决方案

S = 2 * ((N-1)*N*(N+1)/6) = N*(N+1)*(N-1)/3

示例：for N=4 S = 3*4*5/3 = 20

绝对矩阵之和

sum of absolute matrix

java

algorithm

tail-recursion

time-complexity

尾递归

大O