この順列アルゴリズムの空間複雑度はどのくらいですか？

Question

順列を再帰的に計算するこのアルゴリズムの時間的複雑さは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; 
} 

Answer 1

あなたは同時にすべての再帰呼び出しpermutationsOfRest/permutations上に保持していないので、いいえ、スペースの複雑さは、 "単なる" O（N！  ×   N）である。（あなたが持っています一度に2つ、buそれだけで一定の係数のt、そう漸近複雑さには関係ありません。）

注意あなたが実際にがList<String>を必要としない場合、カスタムIterator<String>実装として物事をラップする方がよいかもしれませんすべての順列を一度にメモリに保存する必要はなく、すべての順列を事前に計算する必要はありません。 （もちろん、実現するには少し面倒ですので、Iterator<String>の主な用途はちょうどList<String>をあらかじめ入力するだけの価値がありません）