如何分析Java方法的时间复杂度？求解递归方法复杂度疑问

嘿，我来帮你理清这个困惑！首先先把你的代码贴出来，方便我们一起分析：

int function(int n) { 
    if(n<20) { 
        return 19; 
    } 
    return 20 + function(n/2) + function(n/2); 
}

你之前觉得时间复杂度是O(log n)，这个误解很常见——很多人会看到递归里是n/2，就直接联想到对数级的复杂度，但这里因为每次递归会调用两次自身，情况就不一样了，我们一步步拆解：

1. 写出递归关系式 #

当n ≥ 20时，方法会执行两次function(n/2)，再加上一些常数时间的操作（比如判断、加法），所以时间复杂度的递归式可以写成：

T(n) = 2*T(n/2) + O(1)
其中O(1)代表常数时间的非递归操作。

2. 用主定理推导结果 #

我们可以用主定理来快速求解这个递归式：
主定理针对形如T(n) = a*T(n/b) + f(n)的递归，这里：

• a=2（每次递归调用2次自身）
• b=2（每次问题规模缩小为原来的1/2）
• f(n)=O(1)=n^0（常数级的额外操作）

计算log_b a = log₂2 = 1，因为f(n) = O(n^(log_b a - ε))（这里ε=1>0），符合主定理的第一种情况，所以：

T(n) = O(n^(log_b a)) = O(n^1) = O(n)

3. 用递归树直观理解 #

如果觉得主定理太抽象，我们可以用递归树来可视化：

• 第0层（根节点）：处理规模为n的问题，耗时O(1)，产生2个子节点
• 第1层：2个节点，每个处理规模n/2的问题，每个耗时O(1)，总耗时2*O(1)，产生4个子节点
• 第2层：4个节点，每个处理规模n/4的问题，总耗时4*O(1)，产生8个子节点
• ...
• 第k层：2^{k个节点，每个处理规模n/(2}k)的问题，总耗时2^k*O(1)

当n/(2^k) < 20时，递归停止，此时k≈log₂n。把每一层的耗时加起来：
总耗时 = O(1)(2^0 + 2^1 + 2^2 + ... + 2^log₂n)
这是一个等比数列求和，结果是O(1)(2^(log₂n +1) -1) = O(1)*(2n -1) = O(n)

为什么你会误以为是O(log n)？ #

通常O(log n)的递归是单次调用自身的情况（比如二分查找的递归实现），但这里每次递归会分裂出两个分支，节点数是指数级增长的，最终所有节点的总数是线性的n，所以时间复杂度是O(n)而不是O(log n)。

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