如何计算复杂递归算法的时间复杂度？以something(0,n)为例

好问题！你的猜想其实是对的——这个算法的时间复杂度确实是O(n log n)（和你说的n*ln(n)等价，因为对数的底数在时间复杂度分析中可以忽略常数系数）。下面我们一步步来做正式证明：

1. 定义递归式 #

首先，我们定义T(n)为调用something(b, e)时的时间复杂度，其中问题规模n = e - b（也就是区间[b, e)的长度）。

看函数的执行逻辑：

• 基础情况：当b >= e时，直接返回，时间开销为O(1)。
• 非基础情况：
  • 先执行一个for循环，从i=b到i<e，总共循环n次，每次是简单的自增操作，所以这部分时间开销是O(n)。
  • 然后递归调用两个子问题：something(b, k)和something(k+1, e)，其中k=(b+e)/2。每个子问题的规模都是n/2左右（因为k - b ≈ n/2，e - (k+1) ≈ n/2），所以每个子问题的时间开销是T(n/2)，两个就是2*T(n/2)。

综上，我们可以得到递归关系式：

T(n) = 2*T(n/2) + O(n) ，当n > 0
T(0) = O(1)

2. 用递归展开法证明 #

为了更直观地推导，我们把O(n)替换成常数系数c*n（c是一个固定常数），然后逐层展开递归式：

• 第1层：T(n) = 2*T(n/2) + c*n
• 第2层：T(n) = 2*(2*T(n/4) + c*(n/2)) + c*n = 4*T(n/4) + c*n + c*n = 4*T(n/4) + 2*c*n
• 第3层：T(n) = 4*(2*T(n/8) + c*(n/4)) + 2*c*n = 8*T(n/8) + c*n + 2*c*n = 8*T(n/8) + 3*c*n
• ...
• 第k层：T(n) = 2^k * T(n/2^k) + k*c*n

当递归到基础情况时，n/2^k = 1，也就是k = log₂n（以2为底的对数）。此时T(1) = O(1)，代入上式：

T(n) = 2^log₂n * O(1) + log₂n * c*n

因为2^log₂n = n，所以化简后：

T(n) = n*O(1) + c*n*log₂n

忽略常数项和系数，最终时间复杂度为O(n log n)。而log₂n和ln(n)是常数倍关系（log₂n = ln(n)/ln(2)），所以你说的n*ln(n)其实和O(n log n)是等价的，只是对数底数不同而已。

3. 用主定理快速验证 #

如果你熟悉主定理（Master Theorem），可以直接用它来验证：
主定理针对递归式T(n) = a*T(n/b) + f(n)，其中a≥1，b>1。
这里a=2（每次递归分成2个子问题），b=2（每个子问题规模是原问题的1/2），f(n)=O(n)。
计算log_b a = log₂2 = 1，而f(n)=Θ(n^1)，符合主定理的情况2，因此：

T(n) = Θ(n^log_b a * log n) = Θ(n log n)

这样就正式证明了你的猜想是正确的！

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