python - 2 个递归调用的大 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)

什么是 Big Theta 界限g(n)？

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

仅考虑f(x - 1, y - 1)：需要 n 次递归调用才能到达基本情况，每个调用都分支到另一个f(x - 1, y - 1)。在这一点上，我不知道如何进行。

（答案是 Θ(2 ⁿ )。）

score 1 · Accepted Answer

解决此问题的一种方法是为该问题编写递归关系。如果您注意到，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(n) 由 2 ⁿ⁺¹ - 1 给出，因此运行时间为 Θ(2 ⁿ )。

希望这可以帮助！

1 回答 1