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

Question

问题来自Introduction to Algorithms第 3 版，P63，问题 3-6，它作为Iterated functions 引入。我重写如下:

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) .但让我先解释一下其他界限(只是为了更好地理解)。

长话短说

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)

Improving the upper bound: O(log n) → O(log n / log log n)

Now let us try to improve the upper bound. Instead of dividing n by a fixed constant (namely 2 in the above proof) we divide n as long by the initial value of log(n)/2 as the current value of log(n) is bigger. To be more clearer have a look at the modified code:

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

所以，最后我们“只”需要计算Σ<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)持有。您的示例数据也支持此结果。

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