以下算法的时间复杂度是多少？

Question

给定n个整数的序列,A.为了找到序列的总和,我们遵循以下递归算法,我们创建一个大小为n/2的新序列B,其中B [i] = A [2*i] + A [ 2*i + 1]对于i从0到n/2 - 1并且我们将A替换为B.当A的大小为1时,我们返回元素本身.

时间复杂度不应该如下计算吗？

T(n) = T(n/2) + O(n/2)
or
T(n) = T(n/4) + O(n/4) + O(n/2)
or
T(n) = O(1) + O(2) + O(4) + ... + O(n/4) + O(n/2)

在这一点上,我不确定我是否正确地做了这个值应该等于什么.我假设O(nlgn)

我如何找到解决方案？另外,使用主定理给我O(n),我不确定我是否正确应用主定理.有人可以在这里指导我吗？

Answer 1

首先观察一下

O(1) + O(2) + O(4) + ... + O(n/4) + O(n/2) =
  O(1 + 2 + 4 + ... + n/4 + n/2)

然后你可以在这里认识到几何级数的总和.假设n = 2^m(2的幂为m)

  1 + 2 + 4 + ... + 2^(m-2) + 2^(m-1) = 2^m = n

因此,您的方法为您提供T(n)= O(n).这是与主定理的一致.