python - 计算算法的复杂性以打印 n 对括号的所有有效(即正确打开和关闭)组合

Question

我希望您对我实现的这个算法的时间和空间复杂度有意见(在 Python 中)以计算打印 n 对括号的所有有效(即正确打开和关闭)组合的算法的复杂度(请参阅all valid combinations of n-pair of parenthesis )

def find_par_n(n):
    s = set(["()"])
    for i in range(2, n + 1):
        set_to_add = set()
        for str_ in s:
            set_temp = set()
            ana = set()
            for j in range(len(str_) + 1):
                str_c = str_[0:j] + '(' + str_[j:]
                if str_c in ana:
                    continue
                ana.add(str_c)
                for k in range(j + 1, len(str_) + 1):
                    str_a = str_c
                    str_a = str_a[0:k] + ')' + str_a[k:]
                    set_temp.add(str_a)
            set_to_add.update(set_temp)
        s = set_to_add
    return s

很可能算法可以在时间和空间方面得到改进。请分享您的想法。

Answer 1

要获得最佳结果，请避免套组。如果每种可能性都只生成一次，则可以将它们放入一个向量中。

这是一个非常简单的递归，它比@bcdan 的回答稍慢:

def rget(n):
  if n == 0:
    return ['']
  else:
    return [fst + '(' + snd + ')' for i in range(n)
                                  for fst in rget(i)
                                  for snd in rget(n-i-1)]

如果你想要一个生成器而不是一个完整的结果列表，上面的变体可能是理想的，但是对于一个完整列表的情况，计算从 0 到 n 的每个 j 的结果要快得多，使用先前计算的列表而不是递归调用:

def iget(n):
  res = [['']]
  for j in range(1, n+1):
    res.append([fst + '(' + snd + ')' for i in range(j)
                                      for fst in rget(i)
                                      for snd in rget(j-i-1)])
  return res[n]

事实证明这要快一个数量级(使用 Python 3.3.2)。

为什么有效

您可以将任何平衡字符串分解为两个平衡子字符串。这不是唯一分解，但可以通过选择尽可能短的非空平衡后缀使其唯一。最短的非空平衡后缀具有起始 ( 匹配结束 ) 的属性；如果不是这种情况，它可以分解为两个更短的非空平衡序列。因此，递归包括查找 Fst(Snd) 形式的所有序列，其中 Fst 和 Snd 的大小之和为 n-1.

时间复杂度:

有n对括号的平衡序列的个数是第n Catalan number C_n，即 O(4ⁿn^2/3).上面的代码在 O(n) 中生成每个序列(因为字符串连接需要 O(n) 时间)总复杂度为 O(4ⁿn^5/3)