给定f(x, y)和g(n):
def f(x, y):
if x < 1 or y < 1:
return 1
return f(x - 1, y - 1) + f(x - 1, y - 1)
def g(n):
return f(n, n)
g(n)的大西塔界是什么？
我推断，由于x==y，f(x, y)中的条件永远不为真，因此2个递归调用将决定复杂性。
仅考虑f(x - 1, y - 1)：需要n个递归调用才能到达基本情况，每个调用分支到另一个f(x - 1, y - 1)。在这一点上，我不知道如何继续。
（答案是θ（2n）。）
解决此问题的一种方法是为问题编写递归关系。如果你注意到，f的自变量总是彼此相等（你可以看到这一点，因为它们在对g（n）的调用中开始时是相同的，并且在这一点上总是相等）。因此，我们可以写一个递归关系T（n），它确定f（n，n）的运行时间。
那么T（n）会是什么呢？作为一种基本情况，T（0）将是1，因为一旦n降到0，函数就会做恒定的功。否则，该函数将做大量的工作，然后对大小为n-1的问题进行两次递归调用。因此，我们得到了这种复发：
T（0）=1
T（n+1）=2T（n）+1
从复发的角度来看，我们看到了一种模式：
- T（0）=1
- T（1）=3
- T（2）=7
- T（3）=15
- T（4）=31
- T（n）=2n+1-1
如果你愿意的话，你可以用归纳法来正式证明这一点。由于T（n）是由2n+1-1给出的，因此运行时间是Θ（2n）。
希望这能有所帮助！