时间复杂度：O(n) VS O(2^n)
TimeComplexity : O(n) VS O(2^n)
下面两个函数，为什么第一个的时间复杂度是n，第二个是2^n？
唯一的区别是第二个函数中 return 之前的 +1。我看不出这会如何影响时间复杂度。
int f1(int n){
if (n==1)
return 1;
return f1(f1(n-1));
}
int f2(int n){
if (n==1)
return 1;
return 1+f2(f2(n-1));
}
与函数递归到return的时间有关。
在第一个函数中，你return的1被带到了所有的外面，所以当你到达1时，你立即结束所有嵌套调用。
在第二个函数中，因为 return 递增 1，当您达到 1 时，您会创建更多的嵌套调用。
为了形象化这一点，在您的函数中放置一个 print 语句并检查输出。
在python中就是
def f1 (n):
print (n)
if n < 2:
return 1
return f1(f1(n-1))
def f2 (n):
print (n)
if n < 2:
return 1
return 1 + f2(f2(n-1))
f1(10)
f2(10)
这里的关键见解是 f1 总是 returns 一个，给定任何东西，并且 f1(1) 在恒定时间内计算。
这些函数中的每一个都会导致两次递归调用——首先是内部递归调用，然后是外部递归调用——除非 n 是一个。在这种情况下，该函数将评估零递归调用。
但是，由于函数 f1 总是 returns 1，无论其输入如何，它进行的递归调用之一，即外部递归调用，将始终在 n 个 1 上调用。因此 f1 的时间复杂度减少到 f(n) = f(n-1) 的时间复杂度，即 O(n) - 因为它唯一会进行的其他调用需要 O(1) 时间。
另一方面，当评估 f2 时，内部递归调用将在 n-1 上调用，外部递归调用也将在 n-1 上调用，因为 f2(n) 产生 n。你可以通过归纳法看到这一点。根据定义，f2 of 1 为 1。假设 f2(n) = n。然后根据定义 f2(n+1) 产生 1 + f2(f2(n+1-1))，根据归纳假设，它减少到 1 + (n+1-1) 或只是 n+1。
因此，无论 f2(n-1) 调用多少次，每次调用 f2(n) 都会导致两次。这意味着 O(2^n) 时间复杂度。
下面两个函数，为什么第一个的时间复杂度是n，第二个是2^n？
唯一的区别是第二个函数中 return 之前的 +1。我看不出这会如何影响时间复杂度。
int f1(int n){
if (n==1)
return 1;
return f1(f1(n-1));
}
int f2(int n){
if (n==1)
return 1;
return 1+f2(f2(n-1));
}
与函数递归到return的时间有关。
在第一个函数中，你return的1被带到了所有的外面，所以当你到达1时，你立即结束所有嵌套调用。
在第二个函数中，因为 return 递增 1，当您达到 1 时，您会创建更多的嵌套调用。
为了形象化这一点，在您的函数中放置一个 print 语句并检查输出。
在python中就是
def f1 (n):
print (n)
if n < 2:
return 1
return f1(f1(n-1))
def f2 (n):
print (n)
if n < 2:
return 1
return 1 + f2(f2(n-1))
f1(10)
f2(10)
这里的关键见解是 f1 总是 returns 一个，给定任何东西，并且 f1(1) 在恒定时间内计算。
这些函数中的每一个都会导致两次递归调用——首先是内部递归调用，然后是外部递归调用——除非 n 是一个。在这种情况下，该函数将评估零递归调用。
但是，由于函数 f1 总是 returns 1，无论其输入如何，它进行的递归调用之一，即外部递归调用，将始终在 n 个 1 上调用。因此 f1 的时间复杂度减少到 f(n) = f(n-1) 的时间复杂度，即 O(n) - 因为它唯一会进行的其他调用需要 O(1) 时间。
另一方面，当评估 f2 时，内部递归调用将在 n-1 上调用，外部递归调用也将在 n-1 上调用，因为 f2(n) 产生 n。你可以通过归纳法看到这一点。根据定义，f2 of 1 为 1。假设 f2(n) = n。然后根据定义 f2(n+1) 产生 1 + f2(f2(n+1-1))，根据归纳假设，它减少到 1 + (n+1-1) 或只是 n+1。
因此，无论 f2(n-1) 调用多少次，每次调用 f2(n) 都会导致两次。这意味着 O(2^n) 时间复杂度。