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

Determining time complexity of recursive function

我写了一个计算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) 的非递归算法?

谢谢!

不确定这是否是您想要的,但根据该页面,您可以编写函数来计算 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