这个算法的运行时间是多少？(递归Pascal的三角形)

Question

鉴于以下功能:

Function f(n,m)
   if n == 0 or m == 0: return 1
   return f(n-1, m) + f(n, m-1)

什么是运行时的复杂性f？我知道如何快速和肮脏,但如何正确表征它？是O(2^(m*n))吗？

Answer 1

这是Pascal三角形的一个实例:每个元素都是它上面两个元素的总和,两边都是一个.

所以f(n, m) = (n + m)! / (n! . m!).

现在要知道f计算所需的调用次数f(n, m),你可以构造一个修改过的Pascal三角形:而不是上面元素的总和,考虑1 + sum(调用本身加上两个递归调用).

画出修改后的三角形,你会很快说服自己这是确切的2.f(n, m) - 1.

您可以从斯特林的近似中获得二项式系数的渐近行为.http://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas

f(n, m) ~ (n + m)^(n + m) / (n^n . m^m)

Answer 2

运行时f(n, m)是在O(f(n, m)).通过以下观察可以很容易地验证这一点:

Function g(n, m):
    if n=0 or m=0: return 1
    return g(n-1, m) + g(n, m-1) + 1

该函数f通常被称为g.此外,该函数g被精确调用g(n, m)以评估结果g(n, m).同样,函数f被精确调用g(n, m) = 2*f(n, m)-1以便评估结果f(n, m).

作为@Yves Daoust在他的回答中指出,f(n, m) = (n + m)!/(n!*m!)因此你会得到一个非递归运行O((n+m)!/(n!*m!))的f.