java - 以下程序的复杂性是多少

Question

该程序递归地打印给定字符串的所有可能组合我对 for 循环内递归调用自身的语句感到困惑。是否隐式 n*n，其中 n 是字符串的长度

   public static void getStringCombination(String prefix, String str) {
     System.out.println(prefix);
     for (int i = 0; i < str.length(); i++)
     getStringCombination(prefix + str.charAt(i), str.substring(i + 1));
    }  

Answer 1

虽然我个人总是难以确定这些事情，但我不得不说这是阶乘。第一个提示是，您正在打印所有可能的组合，如果我没记错高中数学的话，这或多或少是阶乘。第二个提示是，您正在执行递归调用的整个字符串上执行 for 循环，因此第一个调用您将执行 N 次递归调用，然后对于下一个递归调用，您将执行 N-1 次递归调用来电等

我必须说，说完这句话后，我有点怀疑自己，以及它是否真的打印了所有可能的组合这一事实......我很肯定它不会打印涉及后面的字符在前面的组合第一个字符。这可能会使我关于它的阶乘的陈述不正确，但我不能说我对此很确定。

编辑

在阅读@Ben S.的答案和测试后，我相当确定你的例子是O(2^n)，我认为Ben S.的“修复”是O(n!)，但看起来我错了，实际上更高。恐怕我无法解释为什么你的例子是 2^n，但我自己仍在思考。