如何计算两个递归函数的时间复杂度？

我来帮你拆解这两个嵌套递归函数的时间复杂度推导过程，先从简单的f1开始，再深入f2：

一、函数f1的时间复杂度分析 #

首先明确f1的代码：

def f1(n):
    if n == 1:
        return 1
    return f1(f1(n-1))

第一步：推导f1的返回值规律 #

我们可以用数学归纳法证明对于所有n≥1，f1(n)=1：

• 基例：当n=1时，f1(1)=1，成立；
• 归纳假设：假设当n=k时，f1(k)=1；
• 归纳步骤：当n=k+1时，f1(k+1)=f1(f1(k))=f1(1)=1，符合结论。

第二步：推导时间复杂度递推式 #

设T(n)为计算f1(n)所需的时间，基例T(1)=O(1)（直接返回1，常数时间）。

对于n>1，计算f1(n)需要做三件事：

1. 调用f1(n-1)，耗时T(n-1)；
2. 用f1(n-1)的返回值（也就是1）调用f1(1)，耗时T(1)=O(1)；
3. 常数时间的判断和返回操作。

因此递推式为：
T(n) = T(n-1) + O(1) + O(1) = T(n-1) + O(1)

展开这个递推式：
T(n) = T(n-1) + C = T(n-2) + 2C = ... = (n-1)C + T(1)
显然这是线性增长的，所以f1的时间复杂度为O(n)，和你的直觉一致。

二、函数f2的时间复杂度分析 #

先看f2的代码：

def f2(n):
    if n == 1:
        return 1
    return 1 + f2(f2(n-1))

第一步：先明确f2的返回值规律 #

同样先算几个小值找规律：

• n=1: f2(1)=1
• n=2: f2(2)=1 + f2(f2(1))=1 + f2(1)=2
• n=3: f2(3)=1 + f2(f2(2))=1 + f2(2)=3
• n=4: f2(4)=1 + f2(f2(3))=1 + f2(3)=4
• ...

用归纳法可以证明对于所有n≥1，f2(n)=n：

• 基例n=1成立；
• 假设n=k时f2(k)=k；
• 当n=k+1时，f2(k+1)=1 + f2(f2(k))=1 + f2(k)=1 + k = k+1，成立。

第二步：推导时间复杂度递推式 #

设T(n)为计算f2(n)的时间，基例T(1)=O(1)。

对于n>1，计算f2(n)的流程是：

1. 先调用f2(n-1)得到结果n-1，耗时T(n-1)；
2. 再用这个结果调用f2(n-1)，又耗时T(n-1)；
3. 最后做常数时间的加法和返回操作。

因此递推式为：
T(n) = T(n-1) + T(n-1) + O(1) = 2*T(n-1) + O(1)

现在解这个递推式：

• T(1) = C（常数）
• T(2) = 2C + C = 3C
• T(3) = 2*3C + C =7C
• T(4)=2*7C +C=15C
• ...
• 可以看出T(n) = (2^n -1)*C，显然是指数级增长，所以f2的时间复杂度为O(2^n)。

关于空间复杂度 #

你已经理解的很对，两个函数的递归深度都是n（每次递归调用n都会减1，直到n=1），所以空间复杂度都是O(n)，因为递归栈的深度是n。

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