递推关系T( n) =T(n / log n)+Θ(1)

Question

这个问题来自算法简介第3版，P63，Problem 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

验证猜想估计问题的核心是得到一个很好的封堵值的估计。

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)

然后，所有的代数计算，你需要你的问题，只是直接跟随。