algorithm - 求以下代码的时间和空间复杂度

Question

以下代码的空间和时间复杂度是多少以及如何

large(n) //n is +ve
{ 
    if(n<=1) 
        return n;

    sum=0;

    for(i=1 to n-1)
        sum=sum+large(i);

    return sum;
}

Answer 1

你有：T(n <= 1) = O(1)和T(n) = T(n-1) + ... + T(1) + O(1)。

解决这个重复，你得到T(n) = O(n!).

此外，您可以观察到large(k)计算O(n)次数。实际上，您可以通过注意到该算法是动态编程的完美候选者来越来越快地加速整个计算！