使用迭代法（递归树）求解递推式T(n)=T(n/4)+T(n/3)+2n

首先明确一个渐近符号的基础规则：Θ(2n)和Θ(n)是完全等价的，渐近复杂度会吸收所有正的常数系数，因此你的两个猜测本质上是同一个结论，我们可以通过递归树的方法验证这个结论是正确的：

1. 递归树逐层代价计算 #

• 第0层（根节点）：仅1个节点，对应原问题规模n，该层代价为2n，向下拆分出2个子问题，规模分别为n/4和n/3
• 第1层：共2个节点，两个节点的代价分别为2*(n/4)、2*(n/3)，该层总代价为 2*(n/4 + n/3) = 2n * (7/12)
• 第2层：共4个节点，由上一层两个节点分别拆分而来，总代价为 2*(n/16 + n/12 + n/12 + n/9) = 2n * (7/12)²
• 以此类推，第k层的总代价固定为 2n * (7/12)^k

2. 总代价上界推导 #

递归树的最大深度由规模下降最慢的分支决定，也就是每次除以3的分支，最大深度为log₃n，当深度超过该值后子问题规模小于1，递归终止。
总代价为所有层代价的和，是公比为7/12的等比数列求和：

T(n) = Σ（k=0到log₃n）2n * (7/12)^k
由于公比7/12 < 1，该无穷等比数列的和收敛，计算得：
无穷项和 = 首项 / (1 - 公比) = 2n / (1 - 7/12) = 24n/5
因此总代价的上界为 O(n)

3. 总代价下界推导 #

仅根节点的代价就已经达到2n，显然有T(n) ≥ 2n，因此总代价的下界为 Ω(n)

最终结论 #

结合上下界可得，该递推关系的时间复杂度为Θ(n)，和你的猜测一致。

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