建立并求解递归函数的递归关系？

Question

我正在学习java递归的过程中，但我陷入了以下问题。

void f(int n) {
    if (n<=1) return;
    f(n/2);
    System.out.writeln("still continuing...");
    f(n/2);
    f(n/2);
}

我对此有两个问题。

1. 如果我们说 T(n) 是程序打印的行数，n 是输入，那么 T(n) 的递推公式是什么？

2. 如何在不使用主定理的情况下解决问题 1 的递推式？

干杯

Answer 1

让我们从 T(n) 值的公式开始。我们知道以下内容：

1. 使用 0 或 1 作为参数调用 f 需要时间 O(1)
2. 使用较大的值调用 f 会调用 3 次 f(n / 2)，并执行恒定量的其他工作。

因此，我们可以得到以下递推式：

• T(1) ≤ 1
• T(n) ≤ 3T(n / 2) + 1

请注意，我在这里使用“+ 1”项而不是“+ O(1)” “ 学期。这在数学上是不确定的，但由于我们正在寻找以大 O 表示法表示的最终结果，所以这不会是太大的问题。

现在，我们将如何尝试解决这个问题？一种选择是为 n 插入一些任意值，看看会发生什么。我们首先（假设 n > 1）

T(n) ≤ 3T(n / 2) + 1

现在，让我们考虑一下对 T(n / 2) 的调用。如果n/2> 1，然后我们就得到了

T(n) ≤ 3T(n / 2) + 1

≤ 3(3T(n / 4) + 1) + 1

= 9T(n / 4) + 3 + 1

现在，让我们将其扩展为增益：

T(n) ≤ 9T(n / 4) + 3 + 1

≤ 9(3T(n / 8) + 3) + 3 + 1

= 27T(n / 8) + 9 + 3 + 1

此时，我们可以看到一种模式正在出现。经过 i 次递归迭代后，我们完成的总工作是

T(n) = 3ⁱT(n / 2ⁱ) + sum(i = 0 到 i - 1)3ⁱ

这个过程当 n / 2ⁱ ≤ 1 时终止，即当 i ≈ lg n 时发生。如果我们插入 lg n，我们得到

T(n) ≤ 3^{lg n}T(1) + sum(i = 0 到 i - 1)3ⁱ)

≤ 3^{lg n} + sum(i = 0 到 i - 1)3^{lg n}

现在，3^{lg n} = 3^{(log3 n / log3 2)} = 3^{log3 n1 / log3 2} = n^{1 / log3 2}，所以整个事情是

T(n) ≤ n^{1 / log3 2} + sum(i = 0 到 (lg n) - 1)3ⁱ

使用几何级数和的公式，可得最后一项是 (3^{lg n} - 1) / 2，最终扩展到 O(n^{1 / log3 2})，所以总的来说，这个表达式是O(n^{1 / log₃ 2})。

但这个公式实在是太难看了。我们可以简化一下吗？好吧，我们确实有这个：

1 / log₃ 2 = log₂ 3

由此可知运行时间为 O(n^{lg 3})，大约为 O(n ^1.58）。

希望这有帮助！

Answer 2

T(n) = 3* T(n/2)+ O(1)

正如定理所示，答案应该是 O(n^(lg 3))。

更详细的内容可以参考Cormen等人的Introduction to Algorithm，见第4章。
递归方程的求解相当复杂。但通常的方法是先猜测，然后用代入法证明。