时间复杂度：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));


}

- user11317524

---

我也不是很“懂”，但是作为一个提示，第二个函数返回语句中额外的 +1 可能就是答案。 - Tim Biegeleisen

你为什么相信这两个的时间复杂度是你所说的那样？你从哪里得到这些值的？ - Lasse V. Karlsen

这是以前考试的答案，所以我认为它是正确的，对吧？ - user11317524

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。你可以通过归纳法来看到这一点。根据定义，f2(1)为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)的时间复杂度。

- jwezorek

Answer 2

这与递归函数返回所需的时间有关。

在第一个函数中，您返回的1被带到所有函数之外，因此当您达到1时，立即结束所有嵌套调用。

在第二个函数中，由于返回值增加了1，当您达到1时，会创建更多的嵌套调用。

为了可视化这一点，请在函数中放置一个打印语句并检查输出。

在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)

- jpnadas