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

Question

开始学习算法。我了解如何从“常规循环”中找到theta符号，例如 T(n) = Tf(n) + g(n)。但是我在这个循环中迷失了方向：问题1-2e：

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

我该选择哪种方法来找到theta？这个循环是什么？我真的不太理解循环内符号的含义。

- Ruslan Osipov

---

Stack Overflow是一个关于编程和开发问题的网站。这个问题似乎不属于编程或开发领域，因此被认为是不符合主题要求的。请在帮助中心查看可以在这里提出哪些话题。也许您可以在Mathematics Stack Exchange寻求更好的答案。 - jww

哇，这是一个来自过去的震撼！这是一个通用的计算机科学问题（测量算法的theta符号），应该将它移动到哪里？这不属于数学，因为这不是一个数学问题。哦，我在StackOverflow上看到了类似的问题--https://dev59.com/enVD5IYBdhLWcg3wXaYd。 - Ruslan Osipov

是的，对此我感到抱歉。之前有个人提出了一个类似的质量很差的问题，他的问题被关闭了。为了报复，他引用了你的问题，结果你也被卷入其中。 - jww

Answer 1

这是使用变量替换的好地方。我们从以下内容开始：

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

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

S(m) = T(2^m)

= 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).

由于我们不再有平方根项收缩事物，因此这个递归似乎更容易处理。特别地，这正好是主定理所处理的内容。具体而言，我们有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)²),

这就是递归的解。

- templatetypedef

---

从 lg k + (lg k) - 1 + (lg k) - 2 + (lg k) - 3 + ... + (lg k) - lg k，你是如何得到 Θ((lg k)2) 的？ - Akhil Nadh PC

这是从总和[1 + 2 + 3 + ... + n = n(n+1)/2]（http://stackoverflow.com/documentation/math/3458/common-summations-in-computer-science/11960/gausss-sum-1-2-3-n#t=201612131856290041474）推导出来的，将n = lg k代入其中。 - templatetypedef

抱歉，我还没有完全理解。您能否提供从lg k + (lg k) - 1 + (lg k) - 2 + (lg k) - 3 + ... + (lg k) - lg k逐步简化的步骤？是的，我知道这个求和式。但是您如何仍然可以简化它？请明确说明。 - Akhil Nadh PC

@AkhilNadhPC 注意到 (lg k) - 1 + (lg k) - 2 + ... + (lg k) - (lg k) 这个式子，反过来写就是 0 + 1 + 2 + ... + (lg k) - 2 + (lg k) - 1 + lg k。 - templatetypedef

我理解的是，对于以下公式： (lg k) - 1 + (lg k) - 2 + ... + (lg k) - (lg k), = (lg k) +(lg k) + ..... +(lg k) -( 1+2+3+4+.... ) = (lg k) +(lg k) + ..... +(lg k) - m(m+1) / 2如何将m与log k联系起来？ - Akhil Nadh PC

那也可以。请注意，这可以简化为(lg k)^2 - m(m+1)/2，其中m = lg k。然后你有(lg k)^2 - (lg k)(lg k + 1) / 2 ~= (lg k)^2 / 2。 - templatetypedef

Answer 2

这是如何使用数学来解决它的方法。我将使用 lnln(n) 而不是 O(lnln(n))。这主要是为了缩短公式的长度，您可以完全使用大O符号。因此：

这意味着：

,

现在来转换这个大求和式，注意到。

整个lnln(n)的求和可以转化为：

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

---

要做到这一点，我们必须找到最新项的合理边界条件。这可以通过尝试几个整数（如0、1、2）来完成。使用2，您将得到：。

---

将k代入我们之前的方程，你会看到最大的项是：

因此，复杂度为： P.S. 你可以在这里查看类似递归的解决方案。

- Salvador Dali