1

我希望您对我（在 Python 中）实现的该算法的时间和空间复杂度提出意见，以计算算法的复杂度以打印 n 对括号的所有有效（即正确打开和关闭）组合（查看所有有效组合n 对括号的)

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

该算法很可能可以在时间和空间方面进行改进。请分享你的想法。

4

5 回答 5

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)]

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

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和SndFst(Snd)的大小之和为n -1。

时间复杂度：

带有n对括号的平衡序列的数量是第n个 加泰罗尼亚数C n，即O(4 n n 2/3 )。上面的代码在 O( n )中生成每个序列（因为字符串连接需要 O( n ) 时间），总复杂度为 O(4 n n 5/3 )

于 2015-07-17T17:27:35.053 回答
0

可能的组合数是加泰罗尼亚数。因此，复杂性至少是该数字指定的复杂性。 https://en.wikipedia.org/wiki/Catalan_number

于 2015-07-17T18:44:06.153 回答
0

让我们尝试一个更简单的版本。

一些定理：

  1. 正确配对的字符串长度均匀。请不要让我证明这一点。
  2. 给定一个正确配对的长度字符串，可以通过在字符串中每个可能的位置插入一对括号2k来构造所有长度的字符串。有这样的职位。2(k + 1)'()'2k + 1
  3. 要生成所有n对，我们需要递归到插入步骤n时间（并获得长度为2n.

请注意，这不足以生成所有唯一正确配对的字符串，因为例如插入()两次()会产生相同的字符串（()()）。然而，作为一个上限，它应该足够了。

def add_parens(s, nparens):    
    if not s:    
       add_parens('()', nparens)    
    max_length = 2 * nparens    
       if len(s) == max_length:    
       print(s)    
    else:    
        for i in range(0, len(s)):    
            add_parens(s[0:i] + '()' + s[i:], nparens)    

n = 5      
add_parens('', n)

时间复杂度：

  1. 空字符串有1插入点。
  2. 有3插入点()。...

总而言之：

T(n) = 1 * 3 * ... * 2n + 1 ~ O(n!)

递归版本的空间复杂度是O(n(2n + 1))，但是我很确定可以将其降低为线性。

于 2015-07-17T16:42:37.143 回答
0

我很好奇，写了我自己的版本。以下是一些规范（这些都在Python 2.7中）：

n=8

我的：21 毫秒

你的：89 毫秒

n=10

我的：294 毫秒

你的：1564 毫秒

def get(n):
    
    def find(current):
        out = []
        last_index = 0
        for j in range(current.count('(')):
            last_index = current.index('(',last_index) + 1
            out.append(current[:last_index] + '()' + current[last_index:])
        return out
        
    seed = '()'
    current = '()'
    temp = set(['()'])
    for i in range(n):
        new = set()
        for thing in temp:
            new.update(find(thing))
        temp = new

    return [a[1:-1] for a in temp]

我认为最大的区别是我的只有 3 个 for 循环，而你的有 4 个。这发生在str.count函数中。使用这个内置可能会显着提高速度。此外，在每个阶段之后，我都确定了重复项，这会按指数级减少时间。

其实我看到的最大的不同是我只在括号后插入，然后在完成后剥离外面的两个。它创建的重复项更少。如此创建，并在删除封闭后((())())简化为正确的形式。(())()()

于 2015-07-17T16:42:46.470 回答
0

递归版本似乎非常简单，它只在有效分支上花费时间：

def gen(sofar, l, r, n):
    """
    sofar: string generated so far
    l: used left parentheses
    r: used right parentheses
    n: total required pairs
    """
    result = []
    if l == n and r == n:
        # solution found
        result.append(sofar)
    else:
        if l > r:
            # can close
            result.extend(gen(sofar + ")", l, r + 1, n))
        if l < n:
            # can open
            result.extend(gen(sofar + "(", l + 1, r, n))
    return result

def generate(n):
    return gen("", 0, 0, n)

print generate(4)
于 2015-07-17T16:52:08.800 回答