c++ - 似乎很难找出这个简单程序的时间复杂度

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.

现在您有了类似于计算阶乘的递归关系，您可以进行数学运算或创建程序来衡量问题的时间复杂度。

希望我的回答能帮助您理解计算时间复杂度的理论。