这个排列算法的空间复杂度是多少？

这个算法递归计算排列的时间复杂度应该是O(n!*n)，但我并不是100％确定空间复杂度。这个排列算法的空间复杂度是多少？

有n递归，以及递归所需的最大空间是n（每种排列* n!（排列数）的空间。是algorithm`的O空间复杂度（N！* N^2）？

static List<String> permutations(String word) { 
    if (word.length() == 1) 
     return Arrays.asList(word); 
    String firstCharacter = word.substring(0, 1); 
    String rest = word.substring(1); 
    List<String> permutationsOfRest = permutations(rest); 
    List<String> permutations = new ArrayList<String>(); //or hashset if I don’t want duplicates 
    for (String permutationOfRest : permutationsOfRest) { 
     for (int i = 0; i <= permutationOfRest.length(); i++) { 
      permutations.add(permutationOfRest.substring(0, i) + firstCharacter + permutationOfRest.substring(i)); 
     } 
    } 
    return permutations; 
}

来源

2016-11-14 alessiop86

任何与n！是O（吓人）:) –

没有，空间复杂度是 “刚” O（ñ！ × ñ），因为你不同时守住所有的递归调用permutationsOfRest/permutations。（你有两次，一次牛逼这只是一个常数因子，因此是不相关的渐进复杂。）

请注意，如果你实际上并不需要一个List<String>，它可能是更好的包裹东西作为自定义Iterator<String>实施，所以你不需要一次保留所有的内存组合，并且在你开始对任何内容进行任何操作之前不需要预先计算所有的排列组合。（当然，这实施起来有点棘手，所以如果主要使用Iterator<String>只是预先填充List<String>，那么这是不值得的。）

来源

2016-11-14 07:27:15 ruakh

这个排列算法的空间复杂度是多少？

回答

相关问题