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

java big-o

2022-09-03 14:44:40

我一直无法理解作者如何获得以下过程的复杂性，该过程生成字符串的所有排列。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));
    }
  }
}

答案 1

该方法的复杂性是因为其他路径成本：O(n^2 *n!)

首先要注意的是，在路径中，每个调用都是，在我们计算的路径中，它与具有复杂性的调用一起计次。String rem=str.substring(0,i)+str.substring(i+1);O(n)elsenpermutationT(n-1)

计算其复杂性等效于求解： ; 次（for 循环）的工作T(n) = n[n+T(n-1)]n(n+T(n-1))

解决这种复发并不容易，如果我没有错，它应该归结为解决：

$\sum_{k=0}^{n-1}\;\frac{n!\;[n-k]}{n-k-1!}$

但是，让我们尝试近似。每个排列（基本情况）表示递归树中的一个节点。这棵树有叶子。每片叶子都有一条通往长度根部的路径。因此，可以安全地假设树中的节点不超过节点。n!nn*n!

这是对的调用次数的上限。由于每个调用的成本都很高，因此复杂性的总体上限为permutationnO(n^2*n!)

希望这有帮助。

答案 2

我迟到了，但我仍然会发布我的答案。

这就是我对自己解释的方式。采用简化的方法，让我们忽略函数的所有步骤：递归步骤除外。permutation(String str, String prefix)

请记住上述内容，函数的时间复杂度可以用递归关系来表示：，其中是输入字符串的长度。扩展后，.--- (*)T(N) = N*T(N-1)NT(N) = N*(N-1)*(N-2)*...3*2*1*T(0)

现在，因为在基本情况下，我们正在打印前缀字符串，而打印长度为N的字符串是O（N）操作。T(0) = O(N)

以上以闭合形式表示（*）：---（1）N*N!

现在考虑函数的以下行：permutationString rem = str.substring(0, i) + str.substring(i + 1);

这又是一个操作，这是为每个递归调用完成的。因此，考虑上述内容并使用上面的表达式（1）取乘积，总运行时复杂度为O(N)N!T(N)

N*N*N! = N^2*N!