运行 递归算法的时间

Question

我遇到一个问题，询问以下递归算法的 运行 时间是多少。

  int func(int A[], unsigned int len)
  {      if(len==1) return A[0];

         unsigned int mid=len/2;
         int a=func(A,mid); //first half
         int b=func(A+mid,len-mid);//second half

         if(a<b) return b;
         else return a;
  }

这段代码只是 returns 给定数组的最大值。

答案是 O(N)，但我不知道如何证明它..（我的第一个猜测是 O(logN)...但它似乎不正确...）

Answer 1

这是写出递归关系的好地方。每个递归调用都会进行恒定量的比较值和计算数组的中间点的工作，然后进行两次递归调用，每次调用都是原始大小的一半。将其写成递归关系，我们得到

T(n) = 2T(n / 2) + O(1)

然后您可以使用主定理来解决这个问题，其求解时间复杂度为 O(n)。或者，您可以考虑此递归树的形状。每个级别都会使递归调用的次数加倍，并且级别的数量将为 O(log n)，因为您重复将 n 减半。这意味着第一层的总调用次数为 1，第二层为 2，第三层为 4，第四层为 8，等等。求和得到

1 + 2 + 4 + 8 + 16 + ... + n

= 2⁰ + 2¹ + 2² + ... + 2^{log n}

= 2^{(log n + 1)} - 1

= 2n - 1

= O(n)

希望对您有所帮助！