如何在这种递归算法中计算大O复杂度

Question

下面的递归代码用于计算对给定数字求和的可能方式。

输入：4

输出：11111121211122213314.有8种（2^（n-1））不同的方法可以得到4。

我想知道这个算法的大O复杂度是多少？我很欣赏处理递归算法的基本思维过程。另一个问题是，为什么方法的数量是2^（n-1）？我无法从算法中计算出来。非常感谢你们！

    public static int recursive(int n, String out){
    int count=0;
    if (n==0) {
        System.out.println(out);
        return 1;
    } else if (n>0) {
        for (int i=1; i<=n; i++){
            count+=recursive(n-i, out+" "+Integer.toString(i));
        }
        return count;
    } else {
        return 0;
    }
}

Answer 1

BigO（阶数）复杂性可能是一个有点松散的术语。它用于算法性能的缩略图估计。

如果你看看你给出的代码，你可以开始想象这个代码不是递归的。在这种情况下，算法的阶数为n（循环的主算法）。递归函数被调用n次，每次调用（n-1）！（n-1阶乘）乘以（n-1..0）。所以在我看来，你的

O（n（n-1）！）=>O（n！）

这是发生了多少字符串附加操作的缩略图（main for循环的内容，这是代码正在做的主要事情）。