括号组合的时间复杂度

Question

括号组合的时间复杂度

algorithmtime-complexitycombinationsparenthesescatalan

10

我尝试解决一个经典问题，即实现一个算法来打印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;
}

据我理解，这个想法是尽可能添加左括号。对于右括号，只有在剩余的右括号数量大于左括号时才添加。如果我们已经使用了所有的左右括号，我们将把新的组合添加到结果中。我们可以确定不会有任何重复的构造字符串。

对于我来说，这种递归就像我们处理树时所做的事情，例如进行前序遍历：每当可能时，我们都会进入左节点，如果不行，我们就向右走，然后我们尝试在此步骤之后立即向左走。如果我们不能，我们就“回来”并向右走，然后重复遍历。在我看来，这里的想法完全相同。

因此，天真地，我认为时间复杂度将是类似于O(log(n))、O(n.log(n))或者带有对数的东西。但是，当我试图搜索相关内容时，我发现了一些叫做“卡特兰数”的东西，我们可以用它来计算括号的组合数量...（https://anonymouscoders.wordpress.com/2015/07/20/its-all-about-catalan/）

你认为时间复杂度是什么？我们能否在这里应用主定理？

- salamanka44

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

这段代码的复杂度为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)个东西，每个东西的成本为c(n)，那么程序的复杂度不能比O(c(n)f(n))更好。在这里，f(n)=Cat(n)，c(n)=2n，因此即使分析代码很困难，你也可以快速获得复杂度的下限。这个技巧会立即让你放弃复杂度是O(log n)或O(n log n)的想法。