大O递归方法

Question

我有一个叫二进制和的方法

Algorithm BinarySum(A, i, n):
Input: An array A and integers i and n
Output: The sum of the n integers in A starting at index i
if n = 1 then
    return A[i]
return BinarySum(A, i, n/ 2) + BinarySum(A, i + n/ 2, n/ 2)

忽略了使一个简单问题变得复杂的事实我被要求找到Big O.这是我的思考过程。对于大小为N的数组，我将进行1 + 2 + 4 .. + N个递归调用。这接近于1到N之和的一半所以我会说它是N（N + 1）/ 4。在进行了这么多次调用后，我需要将它们加在一起。所以我需要再次执行N（N + 1）/ 4次加法。将它们加在一起我们留下N ^ 2作为主导术语。那么这个算法的大O是O（N ^ 2）吗？或者我做错了什么。有二进制递归并且在最终答案中没有2 ^ n或log n感觉很奇怪

Answer 1

在最终结果中实际上有2^n和log n术语......有点像。

对于每个长度为n的子数组的调用，对这个数组的两半进行两次递归调用，加上一定量的工作（if语句，加法，推入调用栈等）。因此，递归关系由下式给出：

在这一点上，我们可以使用Master定理直接得出最终结果 - O(n)。但是让我们通过反复扩展来得出它：

停止条件n = 1给出m的最大值（忽略舍入）：

在步骤（*）中，我们使用几何系列的标准公式。因此，你可以看到答案在某种意义上确实涉及log n和2^n术语，但它们“取消”以给出一个简单的线性项，这与简单的循环相同。