为什么生成括号的时间复杂度是 O(4^n ( sqr root( n)))

Question

我正在使用 Leetcode 生成括号这是方法 -

public class GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        // Resultant list
        List<String> result = new ArrayList<>();
        /// Recursively generate parentheses
        generateParenthesis(result, "", 0, 0, n);
        return result;
    }

    private void generateParenthesis(List<String> result, String s, int open, int close, int n) {
        // Base case
        if (open == n && close == n) {
            result.add(s);
            return;
        }
        // If the number of open parentheses is less than the given n
        if (open < n) {
            generateParenthesis(result, s + "(", open + 1, close, n);
        }
        // If we need more close parentheses to balance
        if (close < open) {
            generateParenthesis(result, s + ")", open, close + 1, n);
        }
    }
}

我从this网站了解解决方案，它说该算法的时间复杂度是

O(4^n(​sqr_root(n)))

，因为第n个加泰罗尼亚数字。有人可以简化这意味着什么以及为什么它是上限

O(4^n(sqr_root(n)))

？

Answer 1

根据Wiki：

C_n - 长度为 2n 的正确括号序列的数量，即 n 个左括号和 n 个右括号的序列，其中左括号的数量等于右括号的数量，并且在其任何前缀中都没有左括号比右括号少。

渐进地，加泰罗尼亚数增长为 (4^n)/(n^(3/2)sqrt(pi))，等于 O(4^n / (nsqrt(n))，但因为我们有为了仅找到有限的序列（大小为 n），我们得到了 O(4^n / sqrt(n)) 时间复杂度。C_n Asymtotic 的proofs之一。在 Wiki 上也有 gen func 的证明。