计算算法的复杂度以打印所有有效(即正确打开和关闭)的 n 对括号组合 [英] Calculating the complexity of algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses

问题描述

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

I would like your opinion on the time and space complexity of this algorithm I implemented (in Python) to calculate the complexity of algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses (see 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

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

Most likely the algorithm can be improved in terms of time and space. Please share your thoughts.

推荐答案

让我们尝试使用更简单的版本.

Let's try with a simpler version instead.

一些定理:

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

1. Properly paired string are of even length. Don't ask me to prove this one, please.
2. Given a properly paired string of length 2k, it is possible to construct all strings of length 2(k + 1) by inserting pairs of parenthesis '()' at every possible location within the string. There are 2k + 1 such positions.
3. To generate all n pairs, we need to recursive into the insertion step n times (and get strings of length 2n.

请注意，这不足以生成所有唯一正确配对的字符串，因为例如将 () 插入 () 会产生两次相同的字符串(()()).但是作为上限应该足够了.

Note that this is not enough to generate all unique properly paired strings, because e.g. inserting () into () yields the same string twice (()()). However as an upper bound it should suffice.

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 个插入点....

1. There is 1 insertion point for the empty string.
2. There are 3 insertion points for (). ...

总之:

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

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

Space complexity for the recursive version is O(n(2n + 1)), however I'm pretty sure it is possible to bring this down to linear.

这篇关于计算算法的复杂度以打印所有有效(即正确打开和关闭)的 n 对括号组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！