3

I am in the process of learning java recurrence but am stuck on the following question.

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

I have two questions about this.

  1. if we say that T(n) is the number of lines that the program prints and n is the input, what would be the recurrence formula for T(n)?

  2. How do I go about solving the recurrence from question 1 without using master theorem?

cheers

4

2 回答 2

3

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

  1. 使用 0 或 1 作为参数调用 f 需要时间 O(1)
  2. 用较大的值调用 f 会调用 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 i T(n / 2 i ) + sum(i = 0 to i - 1)3 i

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

T(n) ≤ 3 lg n T(1) + sum(i = 0 to i - 1)3 i )

≤ 3 lg n + sum(i = 0 to i - 1)3 lg n

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

T(n) ≤ n 1 / log3 2 + sum(i = 0 to (lg n) - 1)3 i

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

但是这个公式真的很丑。我们可以简化它吗？好吧，我们确实有这个：

1 / 日志3 2 = 日志2 3

这给了我们运行时间是 O(n lg 3 )，大约是 O(n 1.58 )。

希望这可以帮助！

于 2012-02-14T02:38:23.283 回答
0 
T(n) = 3* T(n/2)+ O(1)

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

更多细节可以参考 Cormen et 的算法介绍，见第 4 章。递归方程的求解相当复杂。但通常该方法是先猜测，然后使用替换证明。

于 2012-02-14T04:20:10.247 回答