计算递归关系 T(n)=T(n/log n) + Θ(1)。

Question

这个问题来自于《算法导论》第三版P63上的 Introduction to Algorithms，第3-6题，其中被称为迭代函数。我将其改写如下：

int T(int n){
   for(int count = 0; n > 2 ; ++count)
   {
      n = n/log₂(n); 
   }
   return count;
}

然后尽可能紧密地限制 T(n)。

我可以将其设为O(log n)和Ω(log n / log log n)，但它能更紧吗？

PS：使用Mathematica，我已经得知当n=1*10^3281039时，T(n)=500000，同时T(n)=1.072435*log n/ log log n，而系数随着n从1.22943（n = 2.07126*10^235）下降到1.072435（n = 1*10^3281039）。

希望这些信息有所帮助。

- Mike_Dog

---

你试过插入其中一个边界并查看它们是否满足递归关系（可能需要进行简单修改），对吧？ - user1084944

我尝试了Ω，因为我认为它更有可能。事实证明确实如此，因为(log log N=23.3777)可以产生显著的差异，而系数变化很小。@Hurkyl - Mike_Dog

那个有趣的问题属于计算机科学。我已经标记了它。 - Ely

@Elyasin：我觉得这更像是一个微积分问题，而不是计算机科学问题，因为问题的核心是对函数估计的误差分析。 - user1084944

你可能是对的。我认为这不是一个编程问题。直到现在，我只知道计算机科学。 - Ely

Answer 1

看起来下限很好，所以我试图证明上限为O(log n / log log n)。但是首先让我解释一下其他界限（只是为了更好的理解）。

TL;DR

T(n)在Θ(log n / log log n)内。

T(n)在O(log n)内

这可以通过将n := n/log₂n修改为n := n/2来看到。需要O(log₂ n)步骤才能使n ≤ 2成立。

T(n)在Ω(log n / log log n)内

这可以通过将n := n/log₂(n)修改为n := n/m，其中m是log n的初始值。解方程n / (log n)x < 2得到x的值，如下： log n - x log log n < log 2 log n - log 2 < x log log n (log n - log 2) / log log n < x

因此，x ∈ Ω(log n / log log n)。

提高上限：O(log n) → O(log n / log log n)

现在让我们尝试改进上限。我们不再将n除以固定常数（即上面证明中的2），而是将n除以log(n)/2的初始值，直到当前的log(n)值变小为止。具体请查看修改后的代码：

int T₂(int n){
     n_old = n;
     for(int count=0; n>2 ;++count)
     {
         n = n / (log₂(n_old)/2);

         if(log₂(n)) <= log₂(n_old)/2)
         {
            n_old = n;
         }
     }
     return count;
}

函数 T₂ 的复杂度显然是函数 T 的上界，因为整个时间都满足 log₂(n_old)/2 < log₂(n)。

现在我们需要知道每次除以 1/2⋅log(n_old) 的次数：

    n / (log(sqrt(n)))x ≤ sqrt(n)
⇔           n / sqrt(n) ≤ log(sqrt(n))x
⇔          log(sqrt(n)) ≤ x log(log(sqrt(n)))
⇔    log(sqrt(n)) / log(log(sqrt(n)))  ≤ x 

因此，我们得到递归公式 T₂(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n))))。

现在我们需要知道这个公式要扩展多少次，直到 n < 2 成立。

        n2-x < 2
⇔       2-x⋅log n < log 2
⇔       -x log 2 + log log n < log 2
⇔       log log n < log 2 + x log 2
⇔       log log n < (x + 1) log 2

因此，我们需要将公式展开约 log log n 次。

现在变得有点困难。（也可以看看 Mike_Dog's answer）

T₂(n) = T(sqrt(n)) + log(sqrt(n)) / log(log(sqrt(n)))
      = Σk=1,...,log log n - 1 2-k⋅log(n) / log(2-k⋅log n))
      = log(n) ⋅ Σk=1,...,log log n - 1 2-k / (-k + log log n))
(1)   = log(n) ⋅ Σk=1,...,log log n - 1 2k - log log n / k
      = log(n) ⋅ Σk=1,...,log log n - 1 2k ⋅ 2- log log n / k
      = log(n) ⋅ Σk=1,...,log log n - 1 2k / (k ⋅ log n)
      = Σk=1,...,log log n - 1 2k / k

在标有（1）的行中，我重新排列了总和。

因此，最后我们“只需要”计算Σk = 1，...，t 2k / k，其中t = log log n - 1。此时Maple将其解决为

Σ_{k = 1，...，t} 2^k / k = -I⋅π - 2^t⋅LerchPhi(2, 1, t) + 2^t/t

其中I是虚数单位，LerchPhi是Lerch transcendent。由于上述总和的结果对于所有相关情况都是实数，因此我们可以忽略所有虚部。Lerch transcendent LerchPhi(2,1,t)似乎在O(-1/t)内，但我不确定。也许有人会证明这一点。

最后，这导致

T₂(n) = -2^t⋅O(-1/t) + 2^t/t = O(2^t/t) = O(log n / log log n)

总之，我们有T(n) ∈ Ω(log n / log log n)和T(n) ∈ O(log n/ log log n)，

因此T(n) ∈ Θ(log n/ log log n)成立。这个结果也得到了你的示例数据的支持。

希望这能让您理解并有所帮助。

- AbcAeffchen

---

谢谢你的回答。此外，我刚学了一个所谓的“主定理”，可以简化你证明的最后部分，你可以在我的回答中看到。 - Mike_Dog

Answer 2

问题的关键在于验证猜测估计的方法是得到一个好的估计值来插入数值。

n / log(n)

进入函数

n --> log(n) / log(log(n))

定理:

log( n/log(n) ) / log(log( n/log(n) )) = log(n)/log(log(n)) - 1 + o(1)

(如果字体阅读有问题，那是小写的oh，不是大写的oh)

证明：

为了节省符号，我们可以这样写

A = n
B = log(n)
C = log(log(n))

这项工作基于对（自然）对数的一阶近似：当 0 < y < x 时，

log(x) - y/x < log(x - y) < log(x)

我们正在尝试估计的值是：

log(A/B) / log(log(A/B)) = (B - C) / log(B - C)

应用对数差的界限，得到以下结果

(B-C) / log(B) < (B-C) / log(B-C) < (B-C) / (log(B) - C/B)

那就是说，

(B-C) / C < (B-C) / log(B-C) < (B-C)B / (C (B-1))

我们试图满足的递归和下限都表明，我们应该用 B/C - 1 来估计这个。从两边取出它可以得到：

B/C - 1 < (B-C) / log(B-C) < B/C - 1 + (B-C)/(C(B-1))

因此，我们得出结论。

(B-C) / log(B-C) = B/C - 1 + o(1)

---

如果您从这个分析中获取一个想法并用于自己，让它成为使用微分逼近（甚至更高阶泰勒级数）来替换复杂函数的要点。例如，一旦您有了使用此方法的想法。

log(x-y) = log(x) + Θ(y/x) when y = o(x)

然后，你需要进行的所有代数计算都可以直接进行。

- user1084944

Answer 3

感谢@AbcAeffchen的回答。

我是这个问题的提问者，昨天学习了"主方法"的知识后，"稍微困难一点"的证明部分可以简单地如下完成。

我会从这里开始：

T(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n))))
⇔ T(n)=T(sqrt(n)) + O(log n  / log log n)

让

n=2^k，S(k)=T(2^k)

那么我们有

T(2^k) = T(2^k/2) + O(log 2^k / log log 2^k) ⇔ S(k) = S(k/2) + O( k/log k)

使用主方法

S(k) = a*S(k/b)+f(k)，其中 a=1，b=2，f(k)=k/log k = Ω(k^{log₂1 +ε}) = Ω(k^ε)，

只要 ε∈(0,1)

所以我们可以应用情况3。然后

S(k) = O(k/log k)

T(n) = S(k) = O(k/log k) = O(log n/ log log n)

- Mike_Dog

---

这比我的容易多了 :D - AbcAeffchen