java - 打印字符串排列的算法 - 运行时间分析

Question

我有以下代码来打印给定字符串的排列。[为了简单起见并且不要松散对我正在尝试的内容的关注，让我们假设字符串中没有重复的字符]

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 个字符，对置换函数的调用次数为 65。

关于我应该如何找到这段代码的运行时间的任何指示？

Answer 1

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

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

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 的调用，
长度为 2 和
的 12 个调用24 个长度为 1 的调用

总和为 41。Voilá。