大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)

忽略使简单问题复杂化的事实，我被要求找到大 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

最终结果中有 in-fact 2^n 和 log n 项...有点像。

对于长度为 n 的 sub-array 的每次调用，都会对该数组的两半进行两次递归调用，加上恒定的工作量（if-statement，加法，推送到调用堆栈等）。因此递归关系由下式给出：

此时我们可以直接使用大定理直接得出最终结果——O(n)。但是让我们通过重复展开来推导它：

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

在步骤(*)中我们使用了几何级数的标准公式。因此，正如您所见，答案在某种意义上确实涉及 log n 和 2^n 项，但它们 "cancel" 给出了一个简单的线性项，这与简单循环相同。

大O递归方法

Big O Recursive Method

big-o

asymptotic-complexity