以下算法的时间复杂度是多少？
What is the time complexity of following algorithm?
给定一个包含 n 个整数的序列，A.
为了找到我们遵循以下递归算法的序列之和，我们创建了一个大小为 n/2 的新序列 B，其中 B[i] = A[2*i] + A[2*i + 1] 对于i 从 0 到 n/2 - 1，我们用 B 替换 A。当 A 的大小为 1 时，我们 return 元素本身。
时间复杂度不是应该这样计算吗？
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)，我不确定我是否正确地应用了主定理。有人可以在这里指导我吗？
首先观察到
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)。这与主定理一致。
给定一个包含 n 个整数的序列，A. 为了找到我们遵循以下递归算法的序列之和，我们创建了一个大小为 n/2 的新序列 B，其中 B[i] = A[2*i] + A[2*i + 1] 对于i 从 0 到 n/2 - 1，我们用 B 替换 A。当 A 的大小为 1 时，我们 return 元素本身。
时间复杂度不是应该这样计算吗？
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)，我不确定我是否正确地应用了主定理。有人可以在这里指导我吗？
首先观察到
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)。这与主定理一致。