сумма абсолютной матрицы

Question

Вот вопрос из предыдущего HackerEarthВызова -

Рой имеет матрицу размером NxN. Строки и столбцы нумеруются от 0 до N-1. j-я колонка i-й строки содержит абсолютную разницу между i и j. Другими словами, матрица [я] [J] = абс (Ij), где 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. Здесь я пытался две вещи, в основном, чтобы сохранить код, оптимизированный -

1. использовать хвостовую рекурсию, и
2. сохранить время работы этой функции порядка «п»

Так скажите, пожалуйста, Я правильно понял две вещи. Если да, то что еще я могу сделать для оптимизации этого кода. Спасибо за вашу помощь.

Answer 1

Матрица имеет очень простую структуру (я рисую только верхнюю правую половину, нижний левый одно и то же, зеркальные)

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

очевидно, что Kth строка содержит арифметическую прогрессию 0..(N - K - 1), так что сумма

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

и общая сумма (O (N) Solutio п)

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

Более того, в то время как сумма каждой строки является «треугольное» число, сумма треугольных чисел «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

Answer 2

Хвостовая рекурсия

Хвостовая рекурсия не защищает вас от переполнения стека в Java. Некоторые другие языки могут распознать tail-calls и оптимизировать их во время компиляции, чтобы они не расширяли стек.

... Оптимизация хвостового вызова трудно сделать в JVM из-за модели безопасности и необходимость всегда иметь доступную трассировку стека.

(От 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; 
} 

Big-O

сохранить время работы этой функции порядка 'n'

Вы этого не достигли.Это ясно видеть, что есть 2 вложенных циклов над num и num уменьшается, я думаю, что это делает его O (п § п)