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

Question

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

有n次递归，一次递归所需的最大空间是n(每个排列的空间* n!(个数permutations). 算法的空间复杂度为`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;
}

Answer 1

不，空间复杂度“只是”O(n! × n)，因为您不会同时保持所有递归调用'permutationsOfRest/permutations . (您确实一次有两个，但这只是一个常数因子，因此与渐近复杂性无关。)

请注意，如果您实际上并不需要 List<String> , 最好把东西包装成自定义 Iterator<String>实现，这样您就不需要一次将所有排列保存在内存中，也不需要在开始对它们中的任何一个进行任何操作之前预先计算所有排列。 (当然，这实现起来有点棘手，所以如果 Iterator<String> 的主要用途只是预填充 List<String> 无论如何，这是不值得的。)