该算法的 space 复杂度是多少？

Question

这是 Cracking the Coding Interview（第 5^th 版）中的第 9.6 题

实现一个算法来打印 n 对括号的所有有效组合
示例
输入：3
输出："((())), (()()), (())(), ()(()), ()()()"

这是我实现的算法（在Java）

private static Set<String> getAllComb(int n) {
      Set<String> allPoss = new HashSet<String>();
      if(n>0) {
          if(n==1) {
              allPoss.add("()");
          } else {
              Set<String> before = getAllComb(n-1);
              for(String phrase: before) {
                  int length = phrase.length();
                  for(int start = length - 2; start>=0; start--) {
                      if(phrase.charAt(start) == '(') {
                          String phraseToConsider = phrase.substring(0, start+1) + "()" +
                               phrase.substring(start + 1);
                          if(!allPoss.contains(phraseToConsider)){
                              allPoss.add(phraseToConsider);
                          }
                      }
                  }
                  String phraseToConsider = "()" + phrase.substring(0);
                  if(!allPoss.contains(phraseToConsider)){
                      allPoss.add(phraseToConsider);
                  }
              }
          }
      }
      return allPoss;
}

这会产生正确的输出。我知道面试官（至少在亚马逊）喜欢问你解决方案的时间和 space 复杂性。对于时间复杂度，我能够证明该算法在 O(n) 中运行并具有递归关系。我在分析 space 复杂性时遇到问题。我这是一个递归解决方案，所以它至少应该是 O(n) 但是在每次递归调用时，我还生成了一个以 n 为界的集合。总数 space 是 O(n) 因为 n 次递归调用还是 O(n²) 因为每次递归调用 n?

的边界 n 的设置大小

Answer 1

For time complexity, I was able to show that the algorithm runs in O(n) with a recurrence relation

这是错误的。平衡括号的序列数由 Catalan numbers 给出：这样的序列数量呈指数增长。如果你的算法不能是线性的，如果它也正确地解决了问题，因为仅仅输出指数数量的解决方案本身就需要指数时间。

至于内存复杂度，你似乎在递归的每一步 n 存储了 n - 1 的所有解决方案，所以内存复杂度对我来说也是指数级的，加上你的其他字符串在每个步骤中创建和递归调用，这只会增加复杂性。

你可以不使用指数内存解决这个问题：想想你如何摆脱存储所有个以前的序列。

Answer 2

正确匹配括号n对的写法数是第n个加泰罗尼亚数，实际上呈指数增长，而不是二次的。 space 单独输出的复杂度是 O(2^n)；有关加泰罗尼亚数字的快速概览，请参阅 the wikipedia article。

请注意，您不是在每个深度进行单个递归调用，而是可能进行 O(n) 次递归调用。

该算法的 space 复杂度是多少？

What is the space complexity of this algorithm?

algorithm

recursion

time-complexity

space-complexity

catalan