foo算法的复杂度

Question

我有这个问题无法解决。这个 foo 算法的复杂度是多少？

int foo(char A[], int n, int m){
  int i, a=0;
  if (n>=m)
    return 0;
  for(i=n;i<m;i++)
    a+=A[i]  
  return a + foo(A, n*2, m/2);
}

foo 函数的调用方式是：

foo(A,1,strlen(A));

so..我猜它是 log(n) * 内部 for 循环的东西..我不确定它是 log(n) 还是什么..

它可能是 log^2 的 theta （n）？

Answer 1

这是主定理的一个很好的应用：

用 n 和 X = mn 重写：

int foo(char A[], int n, int X){
  int i, a=0;
  if (X < 0) return 0;
  for(i=0;i<X;i++)
    a+=A[i+n]  
  return a + foo(A, n*2, (X-3n)/2);
}

所以复杂度是

T(X, n) = X + T((X - 3n)/2, n*2)

注意到惩罚随着 X 的增加而随着 n 的增加而减少，

T(X, n) < X + T(X/2, n)

所以我们可以考虑复杂度

U(X) = X + U(X/2)

并将其插入到主定理中来找到U(X) = O(X) -->复杂度为 O(mn)

Answer 2

我不确定是否有一种“快速而肮脏”的方法，但你可以使用古老的数学方法。没有花哨的定理，只有简单的方程。

在第 k 级递归（k 从零开始）上，循环将进行 ~ n/(2^k) - 2^k 次迭代。因此，对于0 <= i <= lS = sum(n/2^i) - sum(2^i) >，其中 l 是递归深度。

l 大约为 log(2, n)/2（证明一下）。

将S公式中的各部分分别进行变换，可得。

S = (1 + 2 + .. + 2^l)*n/2^l - (2^(l + 1) - 1) ~= 2*n - 2^(l + 1) ~= 2*n - sqrt(n)

由于除循环之外的每个其他语句只会重复 l 次，并且我们知道 l ~= log(2, n)，因此不会影响复杂性。

所以，最终我们得到O(n)。