java - 如何计算算法的成本？

Question

我必须计算这个算法的成本。

我在考虑指数成本。我尝试了递归关系。 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);
}

Answer 1

据我所知:在每个阶段，我们将问题空间分为四个部分。为了组合子问题的结果，我们将四个整数相加，这个操作发生在恒定时间 O(1) .
假设 n是矩阵的高度 a在问题中，和 m是矩阵的宽度 a在问题中
我们可以使用 n x m 将复杂性可视化为 4-nary 树。叶节点和高度 log4(nm) . .树中的节点总数为O(nm) ，所以复杂度是 O(nm) .
如果没有并行性，这种递归算法不应该比矩阵上的顺序算法快。