3

这是Cracking the Coding Interview（第5版）中的问题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;
}

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

4

2 回答 2

3

对于时间复杂度，我能够证明该算法在 O(n) 中运行，具有递归关系

这是错误的。平衡括号序列的数量由加泰罗尼亚数字给出：有很多这样的序列。如果你的算法也能正确解决问题，它就不可能是线性的，因为仅仅输出指数数量的解决方案本身就需要指数时间。

至于内存复杂度，您似乎在递归n - 1的每一步都存储了所有解决方案n，因此内存复杂度在我看来也是指数级的，加上您在每一步创建的其他字符串和递归调用，只能添加到复杂性。

您可以在不使用指数内存的情况下解决问题：考虑如何摆脱存储所有以前的序列。

于 2015-03-22T21:16:02.280 回答
1

写n对正确匹配括号的方法的数量是第n个加泰罗尼亚数，它实际上是指数增长的，而不是二次增长的。单独输出的空间复杂度是O(2^n)；有关加泰罗尼亚数字的快速概述，请参阅维基百科文章。

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

于 2015-03-22T21:16:34.420 回答