如何分析递归方法的时间复杂度？以给定Java递归函数为例

待分析的Java代码 #

double expRecursive(double x, int n) {
    if (n <= 4) {
        return expIterativ(x, n);
    }

    return expRecursive(x, n/2) *
           expRecursive(x, (n + 1)/2);
}

时间复杂度推导 #

1. 基准情况（n ≤ 4）

当n ≤ 4时，方法直接调用expIterativ(x, n)并返回结果，无递归调用。由于n的取值被限制在1到4的固定小范围，无论迭代方法内部逻辑如何，执行时间都是常数级，即O(1)——输入规模固定，不会随原始n的增大而增长。

2. 递归情况（n > 4）

当n > 4时，方法发起两次递归调用：expRecursive(x, n/2)和expRecursive(x, (n+1)/2)。这两个子问题的规模可近似看作n/2（n足够大时，(n+1)/2与n/2的差距为常数，不影响大O复杂度）。两次递归后的乘法操作是常数时间，因此递推式为：
T(n) = 2*T(n/2) + O(1)

3. 递推式求解

用递归树法推导：

• 递归树高度为log₂n（每次问题规模减半，直到缩小到≤4）
• 每一层节点数为2^h（h为当前层数），每个节点的非递归开销为O(1)，因此每一层总开销为2^h * 1
• 所有层总开销总和为：sum_{h=0}^{log₂n} 2^h = 2^(log₂n + 1) - 1 = 2n - 1，对应大O复杂度为O(n)

用主方法验证：
递推式符合T(n) = a*T(n/b) + f(n)，其中a=2，b=2，f(n)=O(1)=n^0。由于log_b a = log₂2 = 1，且f(n) = O(n^(1-ε))（取ε=1即可满足），属于主方法第一种情况，因此T(n) = O(n^log_b a) = O(n)。

澄清你的困惑

你之前对n ≤4时的推导T(n)=T(n/2)+1是错误的，因为当n ≤4时递归已经终止，不会发起新的递归调用，这一步时间是固定常数，无需代入递推式。

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