python - 确定递归函数的时间复杂度

Question

我编写了一个计算Catalan Numbers的递归函数。递归公式为。

我的代码：

def catalan(n): # We call this function. To my opinion it is more elegant.
    d = dict()
    return catalan_rec(n,d)

def catalan_rec(n,d):
    if n == 0:
        result = 1
    elif n in d: return d[n]
    else:
        result = 0
        for i in range(n):
            result += catalan_rec(i,d)*catalan_rec(n-i-1,d)
        d[n] = result
    return result

现在，很明显递归深度是O(n)。我不确定这个算法的时间复杂度是多少。递归树有 O(n) 个节点，在任何节点（叶子除外）中我们进行两次调用。任何调用都是 O(1)，因为我们只检查字典中是否已经有结果，因此时间复杂度是 O(n)。

我的推理正确吗？

顺便说一句，是否可以选择编写以优于 O(n^2) 的时间复杂度运行的非递归算法？

谢谢！

Answer 1

不确定这是否是您想要的，但根据该页面，您可以编写函数来计算 O(n) 中的加泰罗尼亚语数，如下所示：

def catalan(n):
    num, div = 1, 1
    for x in range(n + 2, 2*n + 1):
        num *= x
    for x in range(2, n + 1):
        div *= x
    return num / div