algorithm - 算法的时间复杂度

我想知道以下算法的最大优点

public List<String> getPermutations(String s){
    if(s.length()==1){
        List<String> base = new ArrayList<String>();
        base.add(String.valueOf(s.charAt(0)));
        return base;
    }

    List<String> combos = createPermsForCurrentChar(s.charAt(0),
                                    getPermutations(s.substring(1));

    return combos;
}
 private List<String> createPermsForCurrentChar(char a,List<String> temp){
    List<String> results = new ArrayList<String>();
    for(String tempStr : temp){
        for(int i=0;i<tempStr.length();i++){
            String prefix = tempStr.substring(0, i);


            String suffix = tempStr.substring(i);

            results.add(prefix + a + suffix);
        }


    }
    return results;
}

这里我认为它是getPermutations，叫做n次，其中n是字符串的长度。
我的理解是
createPermutations是O（l*m），其中l是列表temp的长度，m是temp中每个字符串的长度。
然而，由于我们正在研究最坏情况分析，m在每次递归调用中，temp列表的长度都在不断增长，temp中每个字符串中的字符数也在不断增长。
这是否意味着该算法的时间复杂度为O（n*n）！*N）。或者是O（n*n*n）？

最佳答案

好吧，我只是把这写下来作为一个答案，而不是一长串的评论。
将长度为n的字符串上的getperm的运行时间表示为t（n）。注意，在getPerm内部，它调用getPerm（字符串长度n-1），非常清楚

T(n)=T(n-1) + [run time of createPerm]

注意createPerm有两个嵌套的循环外循环遍历getperm（长度为n-1的字符串）结果的大小，内循环遍历n-1（单个字符串的长度）。getPerm（长度为n-1的字符串）的结果是T（n-1）字符串的列表从这里，我们得到了

[run time of createPerm] = (n-1) T(n-1)

把这个代入上一个方程式，得到

T(n) = T(n-1) + (n-1) T(n-1) = n T(n-1)

T（1）＝1从出口条件。我们可以展开以找到解决方案（或者，也可以使用z-transform:Can not figure out complexity of this recurrence）。因为这是一个简单的方程，所以展开速度更快：

 T(n) = n T(n-1)
      = n (n-1) T(n-2)
      = n (n-1) (n-2) T(n-3) ....
      = n (n-1) ... 1
      = n!

所以t（n）=n！
练习：用归纳法证明这一点：p页
这有道理吗？让我们想想。我们正在创建n个字符的排列：http://en.wikipedia.org/wiki/Permutation。
编辑：注意T（n）=n是o（n！）