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

Question

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

有n次递归，一次递归所需的最大space是n（每个排列的space * n!（排列）。算法的 space 复杂度为 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

不，space 复杂度是 "just" O(n! × n)，因为你不要同时持有所有递归调用'permutationsOfRest / permutations。（您确实一次有两个，但这只是一个常数因子，因此与渐近复杂度无关。）

请注意，如果您实际上 不需要 List<String>，最好将其打包为自定义 Iterator<String> 实现，因此您不需要一次将所有排列保存在内存中，也不需要在开始对它们中的任何一个进行任何操作之前预先计算所有排列。（当然，这实现起来有点棘手，所以如果 Iterator<String> 的主要用途只是预填充 List<String>，那是不值得的。）

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

What's the space complexity of this permutations algorithm?

algorithm

big-o

permutation