时间复杂度：O（n）VS O（2 ^ n）

Question

给定以下两个函数，为什么第一个n的时间复杂度为什么第二个为2 ^ n？

唯一的区别是第二个函数返回之前的+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));


}

Answer 1

这里的主要见解是，给定任何值，f1始终返回1，并且f1（1）在恒定时间内进行求值。

每个函数都会导致两个递归调用-首先是内部递归调用，然后是外部递归调用-除非n为1。在这种情况下，该函数将评估零个递归调用。

但是，由于函数f1始终返回1而不管其输入如何，因此它将始终在n的1上调用它进行的递归调用之一（外部递归调用）。因此，f1的时间复杂度降低为f（n ）= f（n-1），即O（n）－因为它将进行的唯一其他调用需要O（1）时间。

另一方面，当评估f2时，内部递归调用将在n-1上调用，而外部递归调用也将在n-1上调用，因为f2（n）产生n。您可以通过归纳法看到这一点。根据定义，1的f2为1。假设f2（n）= n。然后根据定义，f2（n + 1）产生1 + f2（f2（n + 1-1）），根据归纳假设，其减少为1 +（n + 1-1）或仅n + 1。

因此，对f2（n）的每次调用都会产生两倍的结果，但是对f2（n-1）的调用却很多。这意味着O（2 ^ n）时间复杂度。