LeetCode生成括号算法时间复杂度为何是O(4^n·√n)？

我正在处理LeetCode的「括号生成」问题，以下是我的实现方案：

public class GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        // 结果列表
        List<String> result = new ArrayList<>();
        // 递归生成括号
        generateParenthesis(result, "", 0, 0, n);
        return result;
    }

    private void generateParenthesis(List<String> result, String s, int open, int close, int n) {
        // 基准情况：左右括号都用完，加入结果
        if (open == n && close == n) {
            result.add(s);
            return;
        }
        // 左括号未用完，添加左括号并递归
        if (open < n) {
            generateParenthesis(result, s + "(", open + 1, close, n);
        }
        // 右括号数量少于左括号，添加右括号并递归
        if (close < open) {
            generateParenthesis(result, s + ")", open, close + 1, n);
        }
    }
}

我学习该解法后，了解到它的时间复杂度为O(4^n·√n)，这和第n个卡塔兰数有关。下面简化解释这个结论：

1. 问题本质与卡塔兰数 #

这个问题的核心是生成所有合法的n对括号组合，而合法组合的总数恰好等于第n个卡塔兰数Cₙ。卡塔兰数的计算公式是：
Cₙ = (1/(n+1)) × C(2n, n)
其中C(2n, n)是组合数，代表从2n个位置里选n个放左括号的总可能数（但其中只有卡塔兰数对应的组合是合法的）。

2. 卡塔兰数的渐近增长 #

用斯特林公式（近似阶乘的数学公式）推导后，卡塔兰数的渐近近似值为：
Cₙ ~ 4ⁿ/(n^(3/2)×√π)
这意味着当n很大时，合法括号组合的数量大概是4ⁿ除以√n的规模，也就是Θ(4ⁿ/√n)量级。

3. 时间复杂度的计算 #

你的递归解法中，每个合法组合的生成需要逐步添加2n个字符（每个组合长度是2n），每一步添加字符都对应一次递归调用。因此总操作数是「合法组合数 × 每个组合的生成步骤数」，也就是Cₙ × 2n。

把卡塔兰数的渐近值代入计算：
(4ⁿ/(n^(3/2))) × n = 4ⁿ/(n^(1/2))
忽略常数项后，精确的时间复杂度是O(4ⁿ/√n)。而O(4ⁿ·√n)是一个更宽松的上界——因为1/√n远小于√n，所以4ⁿ/√n必然小于4ⁿ·√n，因此后者可以作为该算法时间复杂度的上界。

内容的提问来源于stack exchange，提问作者Khushi Sharma