首先直接给结论：你认为递归关系式T(n) = 3T(n-1) + n的时间复杂度是O(n³)，这个结论是错误的，正确的时间复杂度应该是O(3ⁿ)。下面我会用递归树方法详细推导，同时解释你错误的核心原因。

你错误的核心原因 #

你只关注了每个节点生成3个子节点，但忽略了两个关键差异：

• 这个递归的深度是n层（因为每次递归调用的参数是n-1，直到触达base case比如n=0，需要n次递归展开），而非分治类递归的对数级深度；
• 每层的总代价不是恒定值，而是随着层数增加按指数级增长的。

像O(n³)这类多项式复杂度，通常出现在分治型递归（比如T(n)=3T(n/3)+n），这类递归的深度是log₃n，节点总数是O(n)，和你现在这种参数线性递减的递归完全不是一个类型。

用递归树的数学化求解方法 #

我们可以通过逐层拆解递归树、求和所有层代价的方式，得到递推式的精确解：

步骤1：构建递归树结构 #

• 第1层（根节点）：对应T(n)，代价为n，节点数1=3⁰；
• 第2层：3个节点，每个对应T(n-1)，单个节点代价为n-1，总代价3*(n-1)，节点数3=3¹；
• 第3层：3²个节点，每个对应T(n-2)，单个节点代价为n-2，总代价3²*(n-2)，节点数3²；
• ...
• 第k层：3^(k-1)个节点，单个节点代价为n - (k-1)，总代价3^(k-1)*(n -k +1)；
• 第n层（base case层）：3^(n-1)个节点，每个对应T(0)（假设base case为常数c），总代价3^(n-1)*c。

步骤2：求和所有层的代价 #

T(n)等于所有层的代价之和，写成数学表达式：

T(n) = Σ（k=1到n）3^(k-1)*(n -k +1) + 3^(n-1)*c

为了方便计算，我们把求和项拆分为两部分：

T(n) = (n+1)*Σ（k=1到n）3^(k-1) - Σ（k=1到n）k*3^(k-1) + 3^(n-1)*c

步骤3：计算两个求和式 #

1. 等比数列求和：Σ（k=1到n）3^(k-1)是首项为1、公比为3的等比数列，结果为：

   (3ⁿ - 1)/(3-1) = (3ⁿ -1)/2
   

2. 等差乘等比数列求和：Σ（k=1到n）k*3^(k-1)是典型的等差乘等比求和，推导后结果为：

   [(2n-1)*3ⁿ + 1]/4
   

步骤4：代入化简 #

把两个求和结果代入原式，通分并合并同类项后，最终可以得到：

T(n) = (9+4c)/4 * 3^(n-1) - (2n+3)/4

从这个结果能明显看出，指数项3ⁿ是主导项，线性项和常数项都可以忽略，因此时间复杂度为O(3ⁿ)。

额外验证：代入法 #

我们也可以用代入法验证这个结论：假设T(n)=a*3ⁿ + bn + d，代入原递推式：

a*3ⁿ + bn + d = 3*(a*3^(n-1) + b(n-1) + d) + n

展开右边并对比系数：

• 3ⁿ项：a=a，恒成立；
• n项：b=3b+1 → b=-1/2；
• 常数项：d=-3b+3d → d=-3/4；

最终得到T(n)=a*3ⁿ - (1/2)n -3/4，和递归树推导的结果一致，进一步验证了复杂度为O(3ⁿ)。

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