0

我有以下代码来打印给定字符串的排列。[为简单起见，不要忘记我正在尝试的内容，假设字符串中没有重复的字符]

public static int count = 0;

public static void permute(String soFar, String strLeft) {

    if(strLeft.length() == 1) {
        soFar += strLeft;
        System.out.println(++count + " :: " + soFar);
    }

    for(int i=0; i<strLeft.length(); i++) {
        permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1));
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    String input = "abcd";
    permute("",input);
}

我试图弄清楚这段代码的运行时间。

到目前为止我的想法链：试图写一个重复，

T(n) = n * T(n-1) + O(n) for n > 1
     = 1                 for n = 1

有n！排列，但递归调用的数量大于 n!。事实上，对于输入字符串为 "abcd" （即 4 个字符）的示例，对 permute 函数的调用次数为 65。

关于我应该如何查找此代码的运行时间的任何指示？

4

1 回答 1

2

好吧，首先，你打了多余的电话。如果只剩下一个字符，则发出一个解决方案。但是你仍然会permute用一个空字符串调用并破坏调用计数。

我的第一个改进是else在if子句中添加一个。

public static void permute(String soFar, String strLeft) {

    if(strLeft.length() == 1) {
        soFar += strLeft;
        System.out.println(++count + " :: " + soFar);
    }
    else {
        for(int i=0; i<strLeft.length(); i++) {
            permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1));
        }
    }
}

这将调用次数减少到 41。为了计算调用次数，构建调用树并计算节点数。由于每次调用都是通过从字符串中删除一个字符来完成的，因此有：
1 个长度为 4 的
调用、4 个长度为 3 的
调用、12 个长度为 2 的
调用和 24 个长度为 1 的调用

总计为 41。瞧。

于 2013-03-05T07:43:09.740 回答