开始学习算法。我了解如何从“定期重复”（如T(n) = Tf(n) + g(n). 但是我迷失了这种重复：问题1-2e：
T(n) = T(√n) + Θ(lg lg n)
如何选择找到 theta 的方法？什么，呃，这个复发是什么？我只是不太明白 notation-inside-a-recurrence 的事情。
问问题
10398 次
2 回答
8
这是使用变量替换的好地方。我们从
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 0 Θ(log m)）。然后，主定理告诉我们，这解决了
S(m) = Θ((log m) 2 )。
我们刚刚求解了递归 S(m)，但我们对求解递归 T(n) 很感兴趣。我们如何连接它们？好吧，由于 S(m) = T(2 m )，我们可以 - 假设 n 是 2 的完美幂 - 将其重写为 S(log n) = T(n)。然后让我们看到
T(n) = S(log n)
= Θ((log log n) 2 ) ,
这是递归的解决方案。
于 2012-06-22T02:17:48.550 回答
2
以下是如何使用数学来解决它。我将使用lnln(n)而不是O(lnln(n)). 这主要是为了减少公式的长度，你可以用 big-O 做同样的事情。所以：
意思就是：
,
现在要转换这个大汇总通知
整个lnln(n)总和可以转换为：
n我们唯一的问题是找到和之间的某种联系k，这可以很容易地从最新的T(...)术语中推导出来。
为此，我们必须为最近的术语找到一个合理的约束条件。这可以通过尝试几个整数来完成，例如0, 1, 2. 与2您一起：
将 k 代入我们之前的等式，您会看到最大的项是：
因此复杂性是：
PS你可以在这里看到类似重复的解决方案
于 2015-12-14T03:23:48.017 回答