查找递归“生成括号”算法的运行时间

Question

我写了一个解决方案来解决这个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

，因为一旦 openCount 和 closeCount 都等于 n，递归树就会停止。最坏的情况是每次调用

generate()

都会调用自身两次，这意味着每个递归树级别的大小加倍。

2*n

级别的大小每增加一倍就意味着

2^(2n)

节点（每个节点都在持续工作）。我们去掉 n 前面的常量，得到

O(2^n)

作为最终的运行时间。

我的想法正确吗？

Answer 1

你不能“放弃”“常数”，因为： 2^2n = (2^n)^2

甚至： (2^2)^n 等于 4^n。

2^n 和 4^n 根本不一样，你可以尝试画出曲线。

据我所知，是

O(2^2n)

。