字符串组合算法的复杂性（递归）

Question

我有一个如下的方法：

如何计算 Big-O？

O(2ⁿ) 还是 O(nⁿ)？

谢谢。

public static void combination(String str, int r) 
{

    int len = str.length();

    if (len == r) myList.add(str);
    if (len == 1) return;

    String newStr = null;
    for (int i = 0; i < len; i++) {
        newStr = str.substring(0, i) + str.substring(i + 1);
        combination(newStr, r);
    }
}

Answer 1

（因为这是家庭作业，只是提示！）

您已经弄清楚代码的作用了吗？对于给定的输入，它会产生多少输出？

这必定是算法运行时间的下限，因为您无法运行得比必须生成的输出数量更快。也许最简单的方法是查看各种输入的列表的大小并将其用作基础。

Answer 2

这是我的提示。

int n = str.length();

Answer 3

尝试将算法转换为方程，例如 X(n+1) = Function(X(n)) 并求解方程。

如果不能，请尝试使用初始情况 X(1) = Function(X(0))，然后 X(2) = Function(X(1)) 等...您会注意到一种模式（并且可能答案与 O(2^n) 或 O(n^n)) 不同。

只是提示！

Answer 4

对于不太复杂的场景，我使用 counter。

public class Combination {

    private static int count;

    public static void main(String[] args) {

        String[] inputs = new String[] {"12345", "1234", "123", "12", "1"};
        for(String input : inputs){
            count = 0;
            System.out.print("output for " + input + " is:");
            combination(input);
            System.out.println("\nCount for input:" + input + " is " + count);  
        }

    }

    private static void combination(String input) {
        combination("", input);
    }

    private static void combination(String prefix, String input) {
        System.out.print(prefix + " ");
        count++;
        int n = input.length();
        for(int i = 0; i < n; i++){
            combination(prefix + input.charAt(i), input.substring(i + 1));
        }
    }
}

解决方案确实是 O(2^n)