确定递归函数的时间复杂度
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
我写了一个计算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