1

该程序递归地打印给定字符串的所有可能组合，我对递归调用自身的 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));
    }
4

2 回答 2

2

尽管我个人总是难以确定此类事情，但我不得不说这是阶乘。第一个提示是，all the possible combination如果我正确地记得我的高中数学，您正在打印或多或少的阶乘。第二个提示是，您正在对执行递归调用的整个字符串进行 for 循环，因此第一次调用您将执行 N 次递归调用，然后对于下一次递归调用，您将执行 N-1 次递归通话等

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

编辑

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

于 2013-10-09T05:50:24.143 回答
0

它应该接近 O(n2)，但是我们不能说这是精确的，因为这是递归的情况。

于 2013-10-09T05:46:38.250 回答