algorithm - 如何找到以下递归代码的时间复杂度？

Question

如何推导出下面程序的运行时复杂度？

public void function(int n){
   if(n==1) return;
   for(int i=0;i<n;i++){
     function(i)
   }
}

function(4);

我的理解是，

T(n) = n(T(n-1));
T(n-1) = (n-1)(T(n-2))
T(n-2) = (n-2)(T(n-2))

用后续展开替换n(T(n-1))后，

T(n) = n((n-1)((n-2)(T(n-2))))

本质上就是

n*(n-1)*(n-2)...1 = n!

但是，在不同的帖子中，我看到这是 2^n 而不是 n!。如果我遗漏了什么，谁能解释一下？

Answer 1

T(n) = n T(n-1) 确实是 O(N!) - 但它是错误的 函数的递归关系。

循环从i = 0运行到i = n-1，也就是说递归调用是function(0)， 函数(1)，函数(2) ...，函数(n-1)。因此递归关系是:

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

有一个巧妙的技巧可以帮助您解决这个问题。考虑 T(n-1) 中的项，并在 T(n) 的旁边写下展开式:

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

看看这是怎么回事？从另一个中减去一个，只剩下带下划线的项 T(n-1):

T(n) - T(n-1) = T(n-1)
T(n) = 2 T(n-1)

这种递归的替代形式现在可以像以前一样解决:

T(n) = 2^2 T(n-2)
     = 2^3 T(n-3)
     = 2^4 T(n-4)
     = ...
     = O(2^n)

q.e.d.