python - 2 次递归调用的 Big Theta 界限

Question

给定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) 的 Big Theta 界是多少？

我推断，由于 x == y，f(x, y) 中的条件永远不会为真，因此 2 次递归调用将决定复杂性。

仅考虑 f(x - 1, y - 1):需要 n 次递归调用才能达到基本情况，每个调用分支到另一个 f(x - 1, y - 1)。此时我不知道如何继续。

(答案是 θ(2ⁿ)。)

Answer 1

解决此问题的一种方法是为该问题编写递归关系。如果您注意到，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) = 2ⁿ⁺¹ - 1

如果您愿意，您可以使用归纳法正式证明这一点。由于 T(n) 由 2ⁿ⁺¹ - 1 给出，因此运行时间为 θ(2ⁿ)。

希望这有帮助!