如何计算这两个函数的时间复杂度？ （递归）
How to calculate time complexity of these two functions? (recursion)
第一个函数：
def f1(n):
if n == 1:
return 1
return f(f(n-1))
第二个函数：
def f2(n):
if n == 1:
return 1
return 1 + f(f(n-1))
现在我明白为什么两个函数的 space 复杂度都是 O(n)，因为递归深度等于 n。
但是关于时间复杂度，我无法像以前使用正常递归方程那样计算它，可以说我们在第一个函数中使用 f(n-1) 而不是 f(f(n-1)) 。那么它将是 T(n) = 1 + T(n-1) = 2 + T(n-2)=... = n 所以 O(n)，我可以直观地理解它可能对 f1 保持不变，因为所有 returns 都是 1 所以我可能有 2n 次迭代，即 O(n) 但我不知道如何正式处理它。
对于 f2 我不知道如何达到时间复杂度，直觉在这里让我失望，我非常感谢任何有关如何分析这些递归调用的帮助。
最终答案是：f1: Time Complexity: O(n), Space Complexity: O(n)。
f2: Time complexity: O(2^n), Space complexity: O(n).
正如我想您意识到的那样，在 f1 中您正在执行两个操作：
- 致电
f1(n - 1)
- 用第一次操作的结果再次调用
f1。
您可以看到用任何东西调用 f1...或至少任何大于零的东西...returns 1.
在第 2 步中，您只是用 1 再次调用 f1，当立即 returns 时。 O(N).
继续 f2。让我们检查一下这个函数的行为。
- 当n = 1时，我们return
1.
- 当n=2时，我们return
1 + f2(1)。我们知道 f2(1) returns 1，所以 f2(2) returns 2.
- 当n=3时，我们return
1 + f2(2)，所以3.
- 等等
所以看起来 f2(n) 只是 returns n.
每次调用 f2 时，我们都在做与 f1 中相同的事情：用 n - 1 调用 self，然后用任何数字再次调用 self。
换句话说，我们用 n - 1 调用了 f2 两次。对于每个 n，我们将调用次数加倍，因此 O(2^N).
第一个函数：
def f1(n):
if n == 1:
return 1
return f(f(n-1))
第二个函数：
def f2(n):
if n == 1:
return 1
return 1 + f(f(n-1))
现在我明白为什么两个函数的 space 复杂度都是 O(n)，因为递归深度等于 n。
但是关于时间复杂度，我无法像以前使用正常递归方程那样计算它，可以说我们在第一个函数中使用 f(n-1) 而不是 f(f(n-1)) 。那么它将是 T(n) = 1 + T(n-1) = 2 + T(n-2)=... = n 所以 O(n)，我可以直观地理解它可能对 f1 保持不变，因为所有 returns 都是 1 所以我可能有 2n 次迭代，即 O(n) 但我不知道如何正式处理它。
对于 f2 我不知道如何达到时间复杂度，直觉在这里让我失望，我非常感谢任何有关如何分析这些递归调用的帮助。
最终答案是：f1: Time Complexity: O(n), Space Complexity: O(n)。
f2: Time complexity: O(2^n), Space complexity: O(n).
正如我想您意识到的那样，在 f1 中您正在执行两个操作：
- 致电
f1(n - 1) - 用第一次操作的结果再次调用
f1。
您可以看到用任何东西调用 f1...或至少任何大于零的东西...returns 1.
在第 2 步中，您只是用 1 再次调用 f1，当立即 returns 时。 O(N).
继续 f2。让我们检查一下这个函数的行为。
- 当n = 1时，我们return
1. - 当n=2时，我们return
1 + f2(1)。我们知道f2(1)returns 1，所以f2(2)returns 2. - 当n=3时，我们return
1 + f2(2)，所以3. - 等等
所以看起来 f2(n) 只是 returns n.
每次调用 f2 时，我们都在做与 f1 中相同的事情：用 n - 1 调用 self，然后用任何数字再次调用 self。
换句话说，我们用 n - 1 调用了 f2 两次。对于每个 n，我们将调用次数加倍，因此 O(2^N).