我无法理解作者如何得到以下过程的O(n ^ 2 * n！)的复杂性,该过程生成字符串的所有排列.
void permutation(String str){
permutation(str,"");
}
void permutation(String str,String prefix){
if(str.length()==0){
System.out.println(prefix);
} else{
for(int i=0;i最佳答案
由于else路径成本,该方法的复杂性为O(n ^ 2 * n！)：
首先注意每次调用String rem = str.substring(0,i)str.substring(i 1);是O(n),
在else路径中,我们计算n次,同时调用具有复杂度T(n-1)的置换.
计算其复杂度等同于求解：T(n)= n [n T(n-1)]; n次(for循环)一项工作(n T(n-1))
但是让我们尝试近似.
每个排列(基本情况)表示递归树中的节点.这棵树有n！叶.每个叶子都有一条到长度为n的根的路径.因此可以安全地假设不超过n * n！树中的节点.
这是对置换的调用次数的上限.由于每个调用成本为n,因此复杂度的总上限为O(n ^ 2 * n！)
希望这可以帮助.
