Я должен рассчитать стоимость этого алгоритма.
Я думал об экспоненциальной стоимости. Я попробовал рекуррентное отношение. 4*T(n/4) + c*n
и в конце ((4^n) - 1)/3
.
Это правильно? Существуют ли другие методы для его расчета?
int m(int a[][]) {
return m1(a, 0, a.length-1, 0, a[0].length-1);
}
int m1(int a[][], int l1, int l2, int c1, int c2) {
if(c1 > c2 || l1 > l2) return 0;
if(c1 == c2 && l1 == l2) return a[l1][c1];
int c = (c1+c2)/2,
l = (l1+l2)/2;
return m1(a, l1, l, c1, c) +
m1(a, l1, l, c+1, c2) +
m1(a, l+1, l2,c1, c) +
m1(a, l+1, l2, c+1, c2);
}