求解非平衡递归树问题求助：T(n)=T(n/3)+T(2n/5)+n³

嘿，我来帮你搞定这个非平衡递归树的问题！你已经尝试画递归树了，卡在计算环节太正常不过——这种有两个不同递归分支的树，确实容易让人在层层累加的时候犯晕。咱们一步步拆解，把它弄明白。

第一步：拆解递归树的层级代价 #

首先，先明确递归树每一层的总代价：

• 第0层（根节点）：只有一个节点，代价就是递归式里的非递归项：n³
• 第1层：根节点拆分成两个子问题，T(n/3)和T(2n/5)，它们的代价分别是(n/3)³和(2n/5)³，所以这一层的总代价是：

  (n/3)³ + (2n/5)³ = n³ * ( (1/3)³ + (2/5)³ )
  

  计算一下括号里的系数：1/27 + 8/125 = (125 + 216)/3375 = 341/3375 ≈ 0.101，这个值小于1，很关键！
• 第k层：每一层的节点都会继续拆分，你会发现每一层的总代价其实是上一层总代价乘以341/3375。换句话说，第k层的总代价是：

  n³ * (341/3375)^k
  

第二步：计算递归树的总代价 #

整个递归树的总代价就是所有层级代价的和，也就是一个无穷等比数列的求和（因为递归会一直拆分到n趋近于0，不过实际计算时我们只需要看收敛性）：

T(n) = n³ + n³*(341/3375) + n³*(341/3375)² + n³*(341/3375)³ + ...

因为公比r=341/3375 < 1，这个等比数列是收敛的，求和公式是首项/(1-公比)，代入后得到：

T(n) = n³ * ( 1 / (1 - 341/3375) ) = n³ * (3375/3034) ≈ 1.112n³

第三步：确定时间复杂度 #

从上面的计算能看出来，不管递归树有多少层（左边分支深度是log₃n，右边是log_(5/2)n，都远小于n的量级），总代价都是常数倍的n³。所以我们可以用渐近符号总结：

T(n) = Θ(n³)

用代入法验证（可选） #

如果你不确定递归树的结论，还可以用代入法验证：

• 假设T(n) ≤ c*n³（c是一个足够大的常数），代入递归式：

  T(n) = T(n/3) + T(2n/5) + n³ ≤ c*(n/3)³ + c*(2n/5)³ + n³ = c*n³*(341/3375) + n³
  

  只要取c ≥ 3375/(3375-341) ≈1.112，就能满足c*n³*(341/3375) +n³ ≤ c*n³，所以T(n)=O(n³)。
• 下界更简单：因为每一层的代价都是正的，所以T(n) ≥n³，即T(n)=Ω(n³)。
• 结合上下界，就得到T(n)=Θ(n³)。

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