括号组合的时间复杂度

Question

我尝试做经典问题来实现一个算法来打印 n 对括号的所有有效组合。

我找到了这个程序（完美运行）：

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, count + 1);
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[count] = ')';
            addParen(list, leftRem, rightRem - 1, str, count + 1);
        }
    }
}

public static ArrayList<String> generateParens(int count) {
    char[] str = new char[count*2];
    ArrayList<String> list = new ArrayList<String>();
    addParen(list, count, count, str, 0);
    return list;
}

据我了解，我们的想法是尽可能添加左括号。对于右括号，只有当右括号的剩余数量大于左括号时，我们才会添加它。如果我们用完了所有的左括号和右括号，我们会将新的组合添加到结果中。我们可以肯定不会有任何重复构造的字符串。

对我来说，这种递归就像我们处理一棵树，例如我们进行预序遍历：我们每次都可能去左节点，否则我们去右，然后我们尝试在这一步之后向左走。如果不能，我们 "come back" 并向右走，然后重复遍历。在我看来，这里的思路完全一样。

所以，天真地，我认为时间复杂度将是 O(log(n))、O(n.log(n)) 或类似对数的东西。但是，当我试图搜索它时，我发现了一个叫做 "number of CATALAN" 的东西，我们可以用它来计算括号组合的数量....(https://anonymouscoders.wordpress.com/2015/07/20/its-all-about-catalan/)

您认为时间复杂度是多少？我们可以在这里应用主定理吗？

Answer 1

此代码的复杂度为 O(n * Cat(n))，其中 Cat(n) 是第 n 个加泰罗尼亚数字。有 Cat(n) 个可能的有效字符串是括号的有效组合（请参阅 https://en.wikipedia.org/wiki/Catalan_number），并且为每个字符串创建一个长度为 n 的字符串。

因为 Cat(n) = choose(2n, n) / (n + 1), O(n * Cat(n)) = O(choose(2n, n)) = O(4^n / sqrt(n))（参见 https://en.wikipedia.org/wiki/Central_binomial_coefficient）。

您的推理有两个主要缺陷。首先是搜索树不平衡：关闭右大括号时搜索的树与添加另一个左大括号时搜索的树大小不同，因此更常见的计算复杂度的方法不起作用.第二个错误是，即使您假设树是平衡的，搜索树的高度也将是 n，找到的叶子数为 O(2^n)。这与二叉搜索树的分析不同，二叉搜索树通常在树中有 n 个东西，高度为 O(log n)。

我不认为这里有任何标准的方法来计算时间复杂度——最终你将重现一些像计算有效括号字符串时所做的数学——而主定理不是将为您提供支持。

但是这里有一个有用的见解：如果一个程序生成f(n)个东西，并且生成每个if的成本为c(n)，那么这个程序的复杂度不可能比O(c(n )f(n))。这里，f(n) = Cat(n) 和 c(n) = 2n，因此即使分析代码很困难，您也可以快速获得复杂度的下限。这个技巧会立即让你放弃复杂度为 O(log n) 或 O(n log n) 的想法。

括号组合的时间复杂度

Time complexity for combination of parentheses

algorithm

combinations

time-complexity

parentheses

catalan