别担心，我来一步步帮你拆解这个递归函数的时间复杂度，搞清楚它的运行规律就不难了！

首先先把你给出的函数代码贴出来，方便我们对照分析：

int mystery(int n ) { 
    int res = 0; 
    for (int i = 0; i < n; i += 2) { 
        res += 1; 
    } 
    if (n <= 0){ 
        return res; 
    } else { 
        return res + mystery(n - 1); 
    } 
}

接下来我们分三步分析：

1. 单次调用的时间开销 #

每次调用mystery(n)时，首先会执行一个for循环：i从0开始，每次加2，直到i < n。我们来算这个循环的执行次数：

• 如果n是偶数（比如n=4），i会取0、2，共2次，也就是n/2次；
• 如果n是奇数（比如n=5），i会取0、2、4，共3次，也就是(n+1)/2次；

不管n是奇数还是偶数，循环的执行次数都和n成线性关系，常数系数在大O表示法里可以忽略，所以单次调用里循环的时间复杂度是O(n)。另外，剩下的变量声明、判断返回这些都是常数时间，不影响整体，所以单次调用mystery(n)的时间开销是O(n)。

2. 递归调用的链条 #

当n>0时，函数会递归调用mystery(n-1)，这个调用会一直持续到n<=0的时候——也就是会依次调用mystery(n)、mystery(n-1)、mystery(n-2)……直到mystery(0)，总共会有n+1次调用。

3. 总时间复杂度计算 #

总时间就是每一次调用的时间开销加起来，用递归式表示的话：

• 当n>0时，T(n) = T(n-1) + O(n)
• 当n<=0时，T(n) = O(1)（因为n<=0时循环不执行，直接返回，是常数时间）

把这个递归式展开后就是：
T(n) = O(n) + O(n-1) + O(n-2) + ... + O(1)

这是一个等差数列的求和，总和等于n(n+1)/2，在大O表示法里，我们只保留最高次项，忽略常数和低次项，所以最终的时间复杂度是O(n²)。

如果是期中复习的话，这类递归+循环的组合题，核心思路就是先拆解单次调用的时间，再理清递归的调用次数和深度，最后把所有开销累加起来就行啦！

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