for循环内递归函数的时间复杂度

Question

如果我们有一个函数：-

int x=0;

int fun(int n)
{
    if(n==0) 
        return 1;

    for(int i=0; i<n;i++)
        x += fun(i);
}

据我所知，时间复杂度可以计算为：-

T(n) = T(n-1) + T(n-2) +...+ T(0).
T(n) = nT(n-1).

T(n) = O(n!).

我对么？

Answer 1

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

// Replace n with n-1
2. T(n-1) = T(n-2) + T(n-3) + .... + T(0)

替换T(n-2) + T(n-3) + .... + T(0)为T(n-1)第一个方程中的

T(n) = T(n-1) + T(n-1)
     = 2 * T(n-1)
     = 2 * 2 * T(n-2) // Using T(n-1) =  2 * T(n-2)
     = 2^n * T(n-n)
     = 2^n * T(0) // Consider T(0) = 1
     = 2^n 

Answer 2

如果您正在测量函数调用（或添加 - 结果是相同的）的数量，则正确的递归关系是：

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

您可以计算前几个值：

 T(0) = 0
 T(1) = 1
 T(2) = 3
 T(3) = 7
 T(4) = 15

您可以由此猜测 T(n) = 2^n - 1，这很容易通过归纳证明来检查。

从某种意义上说，T(n) = O(n!) 是对的，因为 n! > 2^n（对于 n>3），但 T(n) = O(2^n) 是更严格的界限。