math - 设置和解决递归函数的递归关系？

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 会调用 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 to i - 1)3ⁱ

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

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

≤ 3^{lg n} + sum(i = 0 to 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 to (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)。

希望这对您有所帮助!