我有下面的代码来模拟算法的递归行为,因为我没能弄清楚该算法的时间复杂度:
int M(int n)
{
int result = 1;
for (int i = n-1; i >= 0; --i)
{
result += M(i);
}
return result;
}
(图中输入n为3)。 我认为树中节点的数量就是算法的复杂度。如果输入是n,时间复杂度是多少?谢谢!
最佳答案
我的背景不是 CS,但我可以为您提供一种简单的方法来看待这个问题,
所以我拿了纸和笔,开始使用不同的 n 值。
n = 2, cycles = 4
n = 3, cycles = 8
n = 4, cycles = 16
n = 5, cycles = 32.
你可以清楚地看到循环数 = 2^N,因此我们可以得出结论,这个问题的时间复杂度是 O(2^N)。
现在换一种方式来看这个可能是
我们知道
f(0) = 1
f(1) = f(0) + 1 = 2
f(2) = f(1) + f(0) + 1 = 4
...
f(N) = f(N-1) + f(N-2) .. + f(0) + 1 = 2^N.
现在您有了类似于计算阶乘的递归关系,您可以进行数学运算或创建程序来衡量问题的时间复杂度。
希望我的回答能帮助您理解计算时间复杂度的理论。
关于c++ - 似乎很难找出这个简单程序的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43960557/