理解示例12来自Big O表示法的字符串的所有排列 - 破解编码面试

Question

我无法理解作者如何得到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));
    }
  }
}

Answer 1

该方法的复杂性是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!叶子。每个叶子都有一个到 length 根的路径n。所以可以安全地假设n*n!树中的节点不超过节点。

这是调用次数的上限permutation。由于每个调用都需要成本n，因此复杂性的总体上限是O(n^2*n!)

希望这可以帮助。