java – 理解示例12来自Big O表示法的字符串的所有排列 – 破解

发布时间：2020-12-15 01:07:47 所属栏目：Java 来源：网络整理

导读：我无法理解作者如何得到以下过程的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(

我无法理解作者如何得到以下过程的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！)
希望这可以帮助.
                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!