почему сложность времени n * n * n! для приведенного ниже алгоритма печати всех перестановок строки?

Question

я понимаю! потому что строка № 7 должна быть выполнена! раз для программы, чтобы напечатать всю перестановку строки. откуда берется 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));