递归生成括号算法的时间复杂度分析疑问

我针对LeetCode的「生成有效括号」问题编写了递归解法，但对该算法的时间复杂度存在疑问。以下是我的代码：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        resultList = []
        comboList = []
        self.generate(resultList, n, comboList, 0, 0)
        return resultList

    def generate(self, resultList, n, comboList, openCount, closeCount):
        # are we done?
        if (openCount == n and closeCount == n):
            resultList.append(''.join(comboList))

        # can we open?
        if openCount < n:
            comboList.append('(')
            self.generate(resultList, n, comboList, openCount + 1, closeCount)
            comboList.pop()

        # can we close?
        if openCount > closeCount:
            comboList.append(')')
            self.generate(resultList, n, comboList, openCount, closeCount + 1)
            comboList.pop()

我认为时间复杂度应为O(2^{n)：递归树深度为2*n，最坏情况下每个generate()调用会触发两次递归，即每一层节点数翻倍，总节点数为2}(2n)，忽略常数后得到O(2^n)。请问我的分析是否正确？

你的分析不正确，具体原因如下：

• 首先，指数化简错误：2^{(2n)等价于4}n，和O(2^{n)是完全不同的复杂度量级，不能通过忽略常数将4}n简化为2^n。
• 其次，算法存在剪枝逻辑，并非每个递归节点都会触发两次递归：
  • 只有当左括号数量未达n时，才会递归添加左括号
  • 只有当右括号数量少于左括号时，才会递归添加右括号
    这大幅减少了实际递归的节点数，不会达到最坏的O(4^n)情况。
• 该算法的实际时间复杂度为O(4^n / sqrt(n))，这个结论来自卡特兰数的推导：生成的有效括号组合数是第n个卡特兰数，其渐近增长为O(4^n / (n*sqrt(n)))；而每个有效组合最终需要O(n)的时间拼接成字符串，因此总体时间复杂度为O(n * 卡特兰数) = O(4^n / sqrt(n))。

如果只需要粗略的上界，可以表述为O(4^{n)，但绝不能简化为O(2}n)。

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