似乎很难找出这个简单程序的时间复杂性

Question

我有下面的代码来模拟算法的递归行为,因为我没有弄清楚该算法的时间复杂度:

int M(int n)
{
    int result = 1;
    for (int i = n-1; i >= 0; --i)
    {
        result += M(i);
    }
    return result;
}

根据我的理解,我绘制了下面的树来说明算法:

(输入n在图中为3).我认为树中节点的数量是算法的复杂性.如果输入是n,那么时间复杂度是多少？谢谢!

Answer 1

我的背景不是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.

因此,既然您具有类似于计算阶乘的递归关系,您可以进行数学运算或创建程序来测量问题的时间复杂度.

希望我的回答可以帮助您理解计算时间复杂度的理论.