如何分析generateParenthesis算法的时间复杂度？内层循环处理存疑

首先贴出对应的C++代码：

vector<string> generateParenthesis(int n) {
    vector<string> dp[n+1];
    dp[0] = {""};
    dp[1] = {"()"};
    for(int i=2; i<=n; i++) {
        for(int j=0; j<i; j++) {
            for(string& a: dp[j])
            for(string& b: dp[i-1-j])
            {
                dp[i].push_back("("s + a + ")" + b);
            }
        }
    }
    return dp[n];
}

核心逻辑梳理 #

这段代码用动态规划生成n对有效括号的所有组合：

• dp[i]存储i对有效括号的全部组合，其元素个数是第i个卡特兰数（记为C_i）。卡特兰数递推关系为C_0=1，C_1=1，C_i = sum_{j=0}^{i-1} C_j * C_{i-1-j}，渐近增长趋势是O(4^i / i^(3/2))。
• 外层循环从i=2到n，依次计算每一组括号的组合。
• 中间j循环是拆分逻辑：对于i对括号，拆分为"(" + [j对括号组合] + ")" + [i-1-j对括号组合]——用一对括号包裹j对括号，再和剩余的i-1-j对括号拼接，这种拆分能覆盖所有有效组合的可能。
• 最内层两层循环：遍历dp[j]的每个组合a和dp[i-1-j]的每个组合b，将二者拼接成新组合加入dp[i]，这两层循环的总迭代次数等于dp[j]元素数乘以dp[i-1-j]元素数，即C_j * C_{i-1-j}。

时间复杂度拆解 #

1. 内层循环总迭代次数：
   对每个i，将j从0到i-1对应的C_j * C_{i-1-j}求和，根据卡特兰数的递推性质，这个总和恰好等于C_i——也就是dp[i]最终的元素个数。

2. 单次迭代的操作成本：
   每次迭代需要执行字符串拼接"("s + a + ")" + b，生成的字符串长度为2i（i对括号共2i个字符），因此拼接操作的时间复杂度为O(i)。

3. 总时间复杂度：
   我们需要累加从i=2到i=n的所有C_i * O(i)。结合卡特兰数的渐近公式C_i ~ 4^i/(i^(3/2)√π)，可推导C_i * i ~ 4^i/(i^(1/2)√π)，求和后的主导项由i=n时的项决定，因此总时间复杂度为**O(4^n / √n)**。

内层两层循环的困惑解答 #

这两层循环本质是笛卡尔积遍历：把dp[j]的每个组合和dp[i-1-j]的每个组合两两配对，每一对(a,b)都能生成一个新的有效括号组合。比如i=2、j=0时，dp[0]的""和dp[1]的"()"配对生成"()()"；j=1时，dp[1]的"()"和dp[0]的""配对生成"(())"——恰好覆盖了2对括号的所有有效组合。

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