求解递推式T(N)=2T(N−1)+N的Big-O时间复杂度，结果存疑

我来帮你理清楚这个递推式的正确解法，顺便分析下你为什么会得到两种不同结果~

1. 用递推展开法推导精确解 #

我们可以一步步展开递推式，直到触达初始条件T(1)=2：

• T(N) = 2T(N−1) + N
• 代入T(N−1) = 2T(N−2) + (N−1)，得到：T(N) = 2²T(N−2) + 2(N−1) + N
• 再代入T(N−2) = 2T(N−3) + (N−2)，得到：T(N) = 2³T(N−3) + 2²(N−2) + 2(N−1) + N
• 以此类推，直到展开到T(1)，最终可以得到通用形式：

  T(N) = 2^(N−1)T(1) + Σ（i=0 到 N−2）2^i*(N−i)
  

2. 代入初始条件并化简求和 #

把T(1)=2代入第一项：

• 2^(N−1)*2 = 2^N

接下来处理求和部分 Σ（i=0 到 N−2）2^i*(N−i)，我们可以把它拆成两个独立的求和式：N*Σ2^i - Σi*2^i（i从0到N−2）

分别计算这两个和：

• 第一个求和式：Σ（i=0到m）2^i = 2^(m+1)−1，这里m=N−2，结果为2^(N−1)−1，乘以N后得到 N*(2^(N−1)−1)
• 第二个求和式：Σ（i=0到m）i*2^i = (m−1)*2^(m+1)+2，代入m=N−2后得到 (N−3)*2^(N−1)+2

将两个结果相减：

N*(2^(N−1)−1) - [(N−3)*2^(N−1)+2] = 3*2^(N−1) − N − 2

最后合并所有项：

T(N) = 2^N + 3*2^(N−1) − N − 2 = 5*2^(N−1) − N − 2

3. 确定Big-O时间复杂度 #

当N趋向于无穷大时，主导项是5*2^{(N−1)**，低阶项（N和常数）可以忽略，系数5也不影响Big-O的结果。因此这个递推式的时间复杂度是**O(2}N)。

为什么会得到O(N²)的错误结果？ #

大概率是错误套用了主定理导致的。主定理的标准形式是T(n) = aT(n/b) + f(n)，要求b>1，但这里的递推式是T(N)=2T(N−1)+N，相当于b=1，不符合主定理的适用条件，不能强行套用主定理的某个情况（比如误以为f(n)=O(n^log_b a)）。另外也可能是展开递推式时计算求和出现错误，误判了求和项的增长趋势。

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