我试图找到这个 block 的时间复杂度，是 O(n!) 还是 O(2^n)，如何？
void fun(int n)
{
int i;
count++;
if(n>0)
{
for(i=1;i<n;i++)
fun(n-i);
}
}
我尝试了 n 和 count 的差异值赋予值(value)至2^n
??
谢谢
最佳答案
每次调用 T(n) 都会调用 T(n-1), T(n-2), ..., T(1) .
这给了我们复杂性函数:
T(1) = 1
T(n) = T(n-1) + T(n-2) + .... + T(1)
如果我们使用归纳法和假设 T(k) <= c*2^k对于任何 k < n对于一些常数 c (正确检查 T(1) = 1 <= 2^1 后，我们得到:
T(n) = T(n-1) + ... + T(1) + 1 =
= c*2^(n-1) + c*2^(n-2) + ... + c*2^1 + 2^0 <=
<= c*(2^n - 1) <= c*2^n
最后一个等式来自几何级数之和。
因此，我们可以得出T(n)位于Theta(2^n)
关于c - 这个递归函数的时间复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35729755/