algorithm - 生成括号的递归实现时间复杂度分析

Question

当我们有一个递归函数来生成具有 N 个有效括号的括号时，时间复杂度是 Catalan 数的时间复杂度。这对我来说没有意义。

我对时间复杂度的分析是，我们在递归树的每个节点都有两个操作。我们可以添加一个右括号或一个左括号。所以我们进行两次递归调用。

T(n) = 2 * T(N - 1) = O(2^N)

我得到 O(2^N) 作为我的时间复杂度 -- 而不是加泰罗尼亚数字。加泰罗尼亚数字对我来说太武断了——没有意义。谁能进一步解释一下？

Answer 1

在您的假设中，您探索了可以由字符 '(' 和 ')' 组成的所有情况。但是，有可能消除其中一些情况，不是吗？例如，我们知道对于输入 N = 4，"))((" 不是有效/平衡的字符串。事实上，我们知道这是真的从我们放入该字符串的第一个字符的那一刻起。这是 Python 中的递归实现，只是为了让我们可以通过示例观察它。

def generate(index, N, s, depth):
    if index == N:
        print s

    if depth > 0:
        generate(index + 1, N, s + ')', depth - 1)
    if depth < N:
        generate(index + 1, N, s + '(', depth + 1)

本质上，在递归实现中，您会保留当前深度的分数。每当该分数小于 0 时，您就知道您的字符串变得不平衡，因此没有必要进一步探索。因此，与您的假设相反，您不会探索两个子问题。

如果您考虑一下，问题只是找到 N = 2 * K 不同字符的有效排列数。在第一个(最左边)位置，您可以放置​​ K 个字符。 (即所有 '(') 在第二个位置，您可以放置​​一个 ')' 字符，也可以放置一个剩余的 K-1 '(' 字符。通过这种方法，使用重复排列，你可以发现你提到的问题的复杂性确实相当于 K ^th 加泰罗尼亚语数。

基本上，对于长度为 2N 的字符串，您有两个不同的字符，每个字符都有 N。使用permutation with repetition , all 这个字符串的可能排列是 (2N)!/(N!N!)。好吧，第 N^th 加泰罗尼亚数字的公式就是该值除以额外的 (N+1)，如您在 relevant Wikipedia article 中所见.如果您考虑不处理我上面提到的不平衡字符串的情况，您可以看到 (N+1) 因素是由于您没有计算两个子问题的情况。