algorithm - 求解递归：T(n) = T(n^(1/2)) + Θ(lg lg n)

Question

开始学习算法。我了解如何从“定期重复”（如T(n) = Tf(n) + g(n). 但是我迷失了这种重复：问题1-2e：

T(n) = T(√n) + Θ(lg lg n)

如何选择找到 theta 的方法？什么，呃，这个复发是什么？我只是不太明白 notation-inside-a-recurrence 的事情。

Answer 1

这是使用变量替换的好地方。我们从

T(n) = T(√n) + Θ(log log n),

其中参数 n 衰减平方根因子。当你看到这样的东西时，一个很好的常见变换是通过设置 S(m) = T(2 ^m ) 来定义一个新的循环。如果我们在这里这样做，我们会得到以下结果：

S(m) = T( ^2m )

= T(√(2 ^m )) + Θ(log log 2 ^m )

= T(2 ^m/2 ) + Θ(log m)

= S(m / 2) + Θ(log m)。

换句话说，我们现在有递归

S(m) = S(m / 2) + Θ(log m)。

这种重复似乎更容易处理，因为我们不再有平方根项来缩小事情。特别是，这恰好是 Master Theorem 关心的事情。具体来说，我们有 a = 1、b = 2 和 d = 0。（为什么我们有 d = 0？因为我们可以将 Θ(log m) 视为 m ⁰ Θ(log m)）。然后，主定理告诉我们，这解决了

S(m) = Θ((log m) ² )。

我们刚刚求解了递归 S(m)，但我们对求解递归 T(n) 很感兴趣。我们如何连接它们？好吧，由于 S(m) = T(2 ^m )，我们可以 - 假设 n 是 2 的完美幂 - 将其重写为 S(log n) = T(n)。然后让我们看到

T(n) = S(log n)

= Θ((log log n) ² ) ,

这是递归的解决方案。

Answer 2

以下是如何使用数学来解决它。我将使用lnln(n)而不是O(lnln(n)). 这主要是为了减少公式的长度，你可以用 big-O 做同样的事情。所以：

意思就是：

,

现在要转换这个大汇总通知

整个lnln(n)总和可以转换为：

n我们唯一的问题是找到和之间的某种联系k，这可以很容易地从最新的T(...)术语中推导出来。

---

为此，我们必须为最近的术语找到一个合理的约束条件。这可以通过尝试几个整数来完成，例如0, 1, 2. 与2您一起：

---

将 k 代入我们之前的等式，您会看到最大的项是：

因此复杂性是：

PS你可以在这里看到类似重复的解决方案