這個排列算法的空間複雜度是多少？

這個算法遞歸計算排列的時間複雜度應該是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

這個排列算法的空間複雜度是多少？

回答

相關問題