java - 从大O表示理解示例12字符串的所有排列-破解编码面试

我坚持了解作者如何获得以下过程的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<str.length();i++){
        String rem=str.substring(0,i)+str.substring(i+1);
         permutation(rem,prefix+str.charAt(i));
    }
  }
}

最佳答案

该方法的复杂性是O(n^2 *n!)，因为else路径成本高:

首先请注意，每次对String rem=str.substring(0,i)+str.substring(i+1);的调用都是O(n)，
在else路径中，我们计算它的n次数，并调用具有复杂性permutation的T(n-1)。

计算其复杂度等效于解决:T(n) = n[n+T(n-1)]; n时代(for循环)(n+T(n-1))的工作

解决这种重复并不是那么容易，如果我没记错的话，应该归结为解决:

但是，让我们尝试一下。
每个排列(基本情况)代表递归树中的一个节点。这棵树有n!叶。每片叶子都有到n长度根的路径。因此可以安全地假设树中的n*n!节点不多。

这是对permutation的调用次数的上限。由于此调用的每个调用都需要n，因此复杂度的总体上限为O(n^2*n!)
希望这可以帮助。