时间戳

首页 > 解决方案 > TimeComplexity : O(n) VS O(2^n)

time - TimeComplexity : O(n) VS O(2^n)

问题描述

Given the following two functions, why is the time complexity of the first n while the second is 2^n?

The only difference is the +1 before the return in the second function. I don't see how that can influence the time complexity.

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


}

标签： timetime-complexitycomplexity-theory

解决方案

这里的关键见解是 f1 总是返回一个，给定任何东西，并且 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 of 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) 时间复杂度。

推荐阅读