查找递归调用位于 for 循环中的函数的时间复杂度

Question

这是我的功能：

function a(n)

     print 'a'
     if n == 0:
        return 
     for (int i = 0; i<=n-1; i++):
        a(i)
     return

所以基本上我明白，对于每个调用，我们还会递归地调用所有导致 n 的函数编号，然后对于每个函数我们再次执行相同的操作。然而，我的主要问题是 for 循环每次都会跳转到一个变量，所以这就像在递归中进行递归。

Answer 1

它首先终止吗？

对于

n == 0

，它只是返回。但对于

n == 1

，它会调用自己为

n == 0

、

n == 1

和

n == 2

。因此调用

a(1)

将导致再次调用

a(1)

...

IOW，这是一个无限循环，将显示出无限的复杂性。

---

现在算法改变后它将终止。所以让我重新调查一下。

对于

n == 1

它只会用

n == 0

来调用自己。

对于

n == 2

，由于

n == 0

，它会调用自己为

n == 1

、

n == 0

和另一个

n == 1

；拨打 3 个电话。

对于

n == 3

，它会调用自己 3 次 + 3 次 + 1 次，即 7 次。

对于

n == 4

，它会调用自己4次+7次+3次+1次，总共15次。

这看起来非常像 O(2^n - 1) = O(2^n)。

（通过归纳很容易证明；调用次数将为 2^n - 1，这显然对于上面的所有示例都是正确的。鉴于它对于某些 n 是正确的，很容易得出对于 n + 1 它也是正确的)

---

由于归纳证明对于OP来说并不明显，所以这里是：

首先，由于除了循环之外，函数内实际上没有发生任何事情，因此每次迭代只会添加恒定数量的操作，这意味着计算对自身的调用就足够了。

由上式得证

n = 1

。

现在假设它已经被某些人证明了

n

。现在我们将遵循对于

n + 1

来说这是正确的。

根据归纳假设，调用

a(n + 1) = n + 1 + \sum_{i=0}^n (2^i - 1)

的次数（抱歉，这个符号；它本来可以在 mathexchange 上使用。它指出“i 从 0 到 (2^i - 1) 的 n 的总和”）。

现在

n + 1 + \sum_{i=0}^n (2^i - 1) = \sum_{i=0}^n (2^i) = 2^{n + 1} - 1

必须展示。

这证明复杂度是O(2^n)。

Answer 2

@Ronald 的分析绝对正确。

这是程序的不同版本，用于计算不同值

n

发生递归的次数

public class FindingRec
{

   static int count;

   static void rr(int n)
   {
      count++;
      // System.out.print(n + ", ");
      if (n == 0)
         return;

      for (int i = 0; i < n; i++)
      {
         rr(i);
      }
   }

   public static void main(String[] args)
   {
      for (int n = 0; n < 10; n++)
      {
         count = 0;
         rr(n);
         System.out.println("For n = " + n + ", Count: " + count);
      }
   }
}

这是输出：

For n = 0, Count: 1
For n = 1, Count: 2
For n = 2, Count: 4
For n = 3, Count: 8
For n = 4, Count: 16
For n = 5, Count: 32
For n = 6, Count: 64
For n = 7, Count: 128
For n = 8, Count: 256
For n = 9, Count: 512

所以，复杂度正是 O(2^n)。

Answer 3

在第一次调用时，循环运行 n 次，并将递归地调用自身 T(n-1), T(n-2).. T(0)

因此，T(n) = n + T(n-1) + T(n-2) + .... + T(0)。 - (一)

与 T(n-1) 类似，循环将运行 n-1 次，并使用 T(n-2), T(n-3) ... T(0) 调用自身

或者，T(n-1) = n - 1 + T(n-2) + T(n-3) + .. + T(0) - (ii)

将(ii)代入(i)

我们得到，T(n) = n + n - 1 + 2* (T(n-2) + T(n-3) + ... + T(0))

继续 T(n-2)

T(n) = n + n -1 + n - 2 + 2* 2*(T(n-3) + ... + T(0))

或者，T(n) = n*n - (1 + 2 + 3 + ...+n) + 2 * 2 * 2 * ....*T(0)

或者，T(n) = n^2 - n^2 + 2^n [因为 T(0) = 1]

最终答案：T(n) = 2^n