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

Question

题目出自Introduction to Algorithms第3版，P63，问题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)。

此信息是否有用。

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)<sup>x</sup> < 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 的初始值作为 [=] 的当前值30=] 更大。为了更清楚地查看修改后的代码：

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次。

现在有点难了。 （另请参阅 ）

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) 的行中，我重新排序了总和。

所以，最后我们"only"必须计算Σ<sub>k=1,...,t</sub> 2<sup> k</sup> / k 对于 t = log log n - 1。此时 Maple 将此解决为

Σk=1,...,t 2k / k = -I⋅π - 2t⋅LerchPhi(2, 1, t)  +2t/t

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

最终结果是

T₂(n) = -2t⋅O(-1/t) + 2t/t = O(2t/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) 成立。您的示例数据也支持此结果。

我希望这是可以理解的并且能有所帮助。

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)

（如果出现字体可读性问题，那是小哦，不是大哦）

证明：

为了节省符号，写

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)

那么您的问题所需的所有代数计算都直接遵循即可。

Answer 3

感谢@AbcAeffchen 的回答

本人是题主，利用昨天学到的"the master method"知识，证明的"a little bit harder"部分可以简单的做如下。

我将从这里开始：

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), where 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)