java - 为什么时间复杂度是n*n*n!对于以下算法打印字符串的所有排列？

Question

我明白了!因为第7行必须执行n!程序打印字符串所有排列的次数。 n*n从何而来，不是小于n吗!所以应该被忽略。

1. void perm(String str){
2.    perm(str, "");
3.  }
4.
5. void perm(String str, String prefix){
6.     if(str.length() == 0){
7.         System.out.println(prefix);
8.     } else{
9.        for(int i = 0; i < str.length(); i++){
10.           String rem = str.substring(0, i) + 
                           str.substring(i + 1);
11.           perm(rem, prefix + str.charAt(i));
12.       }
13.    }
14. }

Answer 1

可能是因为字符串连接困难。尝试使用 StringBuilder :

StringBuilder rem = new StringBuilder();
rem.append(str.substring(0, i)).append(str.substring(i + 1))
perm(rem.toString(), prefix + str.charAt(i));