如何求解sum1递归算法的时间复杂度？T(n)=1+2*T(n/2)是否正确？

先把代码贴出来方便参考：

func sum1(x []int) int { // Returns the sum of all the elements in the list x.
    return sum(x, 0, len(x)-1)
}
func sum(x []int, i int, j int) int { // Returns the sum of the elements from x[i] to x[j]
    if i > j {
        return 0
    }
    if i == j {
        return x[i]
    }
    mid := (i + j) / 2
    return sum(x, i, mid) + sum(x, mid+1, j)
}

一、判断递推式 T(n) = 1 + 2*T(n/2) 是否正确 #

首先明确T(n)的定义：它表示处理包含n个元素的子数组（也就是j - i + 1 = n）时，sum函数执行的常数时间操作步数。

我们分场景验证：

• 基准情况（n=0或n=1）：
  • 当n=0（对应i>j）：函数只做一次判断就返回0，步数为1；
  • 当n=1（对应i==j）：先后做两次判断，然后返回元素值，步数也为1。
• 递归情况（n>1）：
  此时函数会执行：两次条件判断（都不成立）、计算mid、发起两次递归调用（分别处理左右两个约n/2元素的子数组）、最后将两个递归结果相加。所有这些当前层的操作加起来是常数步数——在时间复杂度分析中，我们通常把常数项简化为1，所以递推式T(n) = 1 + 2*T(n/2)（n>1，基准情况T(1)=1）是完全正确的。

二、求解该递归算法的时间复杂度 #

这里提供两种常用的分析方法：

方法1：递推展开法

假设n是2的幂（即n=2^k，k为正整数，非2的幂的情况分析逻辑一致，最终复杂度结果相同），我们逐层展开递推式：

T(n) = 1 + 2*T(n/2)
= 1 + 2*(1 + 2*T(n/4)) = 1 + 2 + 4*T(n/4)
= 1 + 2 + 4 + 8*T(n/8)
...
= 1 + 2 + 4 + ... + 2^{k-1} + 2^k*T(1)

因为n=2^k，所以k=log₂n，2^k = n。而1+2+4+...+2^{k-1}是首项为1、公比为2的等比数列，求和结果是2^k -1 = n-1。代入基准情况T(1)=1：

T(n) = (n-1) + n*1 = 2n -1

显然，2n-1的时间复杂度是Θ(n)，用大O表示法就是O(n)。

方法2：主定理（Master Theorem）

主定理是分析分治递归复杂度的快捷工具，适用于T(n) = a*T(n/b) + f(n)形式的递推式：

• 这里a=2（每次递归拆分出2个子问题）；
• b=2（每个子问题的规模是原问题的1/2）；
• f(n)=1（当前层的操作是常数时间，属于O(n^0)）。

计算log_b a = log₂2 =1，由于f(n)=O(n^{1-ε})（取ε=1>0，显然n^0 <n^1），符合主定理的第一种情况，因此：

T(n) = Θ(n^{log_b a}) = Θ(n^1) = Θ(n)

简单总结下：这个递归求和算法的时间复杂度是线性的O(n)，你给出的递推式是正确的。

内容的提问来源于stack exchange，提问作者bullbo