请分析方法public int f(int n)的Big O表示法并说明原因

咱先把代码摆出来，方便拆解：

public int f(int n) {
    if (n <= 0) {
        return 0;
    }
    return f(n/2) + n;
}

核心递归结构拆解 #

每次调用f(n)时，除了递归调用f(n/2)，剩下的操作都是常数时间：判断n <= 0的条件分支，以及最后把递归结果和n相加的操作——这俩步骤不管n多大，耗时都是固定的，记为O(1)。

由此我们可以写出递归时间复杂度的表达式：
T(n) = T(n/2) + O(1)
这里T(n)代表处理输入规模为n的问题所需的时间。

两种方法验证时间复杂度 #

1. 递归树法

把递归调用展开成树状结构看：

• 第1层：处理n，耗时O(1)，触发对f(n/2)的调用
• 第2层：处理n/2，耗时O(1)，触发对f(n/4)的调用
• ...
• 直到某一层，n/(2^k) <= 0，递归终止。这里k的取值是log₂(n)——因为每次n减半，经过log₂(n)次后n会变成1，再调用一次就到0了。

整个递归树一共有log₂(n) + 1层，每层耗时都是O(1)，所以总时间复杂度就是O(log n)。

2. 主定理法

这个递归式完美符合主定理的标准形式T(n) = a*T(n/b) + f(n)，对应参数：

• a=1：每次递归只生成1个子问题
• b=2：子问题的规模是原问题的1/2
• f(n)=O(1)=O(n⁰)：非递归部分的耗时是常数级

计算log_b a = log₂(1) = 0，而f(n)和n⁰是同阶的，属于主定理的第二种情况，因此：
T(n) = Θ(n⁰ * log n) = Θ(log n)
也就是时间复杂度为O(log n)。

容易踩坑的混淆点 #

很多人会误以为时间复杂度是O(n)，因为函数的返回值是n + n/2 + n/4 + ... + 1 = 2n - 1（等比数列求和），但返回值的大小和时间复杂度完全是两码事——时间复杂度衡量的是算法执行的操作次数，而非计算结果的数值规模。这里每次递归只有常数级操作，总操作次数和递归深度成正比，也就是log n量级。

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