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

Question

问题来自于算法导论第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从from 1.22943(n = 2.07126*10^235)到1.072435(n = 1*10^3281039)下降.

愿这些信息有所帮助.

Answer 1

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

\n\n

长话短说

\n\n

T(n)是在\xce\x98(log n / log log n).

\n\n

T(n) 位于O(log n)

\n\n

n := n/log\xe2\x82\x82n这可以通过修改来看到n := n/2。
\n它需要O(log\xe2\x82\x82 n)一些步骤才能n \xe2\x89\xa4 2成立。

\n\n

T(n) 位于\xce\xa9(log n / log log n)

\n\n

这可以通过修改 来看出n := n/log\xe2\x82\x82(n)，n := n/m其中m是 的初始值log n。\n解
方程\n得出n / (log n)x < 2x

\n\n

\n log n - x log log n < log 2\n \xe2\x87\x94 log n - log 2 < x log log n\n \xe2\x87\x94 (log n - log 2) / log log n < x\n\n \xe2\x87\x92 x \xe2\x88\x88 \xce\xa9(log n / log log n)\n

\n\n

改进上限：O(log n) \xe2\x86\x92 O(log n / log log n)

\n\n

现在让我们尝试改进上限。我们不是除以n一个固定常数（即2在上面的证明中），而是除以当前值较大n的初始值。为了更清楚地看一下修改后的代码：log(n)/2log(n)

\n\n

int T\xe2\x82\x82(int n){\n     n_old = n;\n     for(int count=0; n>2 ;++count)\n     {\n         n = n / (log\xe2\x82\x82(n_old)/2);\n\n         if(log\xe2\x82\x82(n)) <= log\xe2\x82\x82(n_old)/2)\n         {\n            n_old = n;\n         }\n     }\n     return count;\n}\n

\n\n

函数的复杂度T\xe2\x82\x82显然是函数 的上限T，因为log\xe2\x82\x82(n_old)/2 < log\xe2\x82\x82(n)它始终成立。

\n\n

现在我们需要知道分别除以多少次1/2\xe2\x8b\x85log(n_old)：

\n\n

\nn / (log(sqrt(n))) x \xe2\x89\xa4 sqrt(n)\n\xe2\x87\x94 n / sqrt(n) \xe2\x89\xa4 log(sqrt(n)) x \n\xe2\x87\x94 log(sqrt(n)) \xe2\x89\xa4 x log(log(sqrt(n)))\n\n\xe2\x87\x94 log(sqrt(n)) / log(log(sqrt(n))) \xe2\x89\xa4 x \n

\n\n

这样我们就得到了递推公式T\xe2\x82\x82(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n))))。

\n\n

现在我们需要知道这个公式需要多久展开一次才能n < 2成立。

\n\n

\nn 2 -x < 2\n\xe2\x87\x94 2 -x \xe2\x8b\x85log n < log 2\n\xe2\x87\x94 -x log 2 + log log n < log 2\n\ xe2\x87\x94 日志 日志 n < 日志 2 + x 日志 2\n\xe2\x87\x94 日志 日志 n < (x + 1) 日志 2\n

\n\n

所以我们需要将这个公式展开关于log log n次数。

\n\n

现在变得有点困难了。（也可以看看Mike_Dog 的回答）

\n\n

\nT\xe2\x82\x82(n) = T(sqrt(n)) + log(sqrt(n)) / log(log(sqrt(n)))\n = \xce\xa3 k=1,. ..,log log n - 1 2 -k \xe2\x8b\x85log(n) / log(2 -k \xe2\x8b\x85log n))\n = log(n) \xe2\x8b\x85 \xce \xa3 k=1,...,log log n - 1 2 -k / (-k + log log n))\n(1) = log(n) \xe2\x8b\x85 \xce\xa3 k= 1,...,log log n - 1 2 k - log log n / k\n = log(n) \xe2\x8b\x85 \xce\xa3 k=1,...,log log n - 1 2 k \xe2\x8b\x85 2 - log log n / k\n = log(n) \xe2\x8b\x85 \xce\xa3 k=1,...,log log n - 1 2 k / (k \ xe2\x8b\x85 log n)\n = \xce\xa3 k=1,...,log log n - 1 2 k / k\n

\n\n

在标有 (1) 的行中，我重新排序了总和。

\n\n

因此，最后我们“只需”计算。此时，Maple 解决了这个问题\xce\xa3k=1,...,t 2k / kt = log log n - 1

\n\n

\n\xce\xa3 k=1,...,t 2 k / k = -I\xe2\x8b\x85\xcf\x80 - 2 t \xe2\x8b\x85LerchPhi(2, 1, t) +2 t /t\n

\n\n

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

\n\n

最终结果是

\n\n

\nT\xe2\x82\x82(n) = -2 t \xe2\x8b\x85O(-1/t) + 2 t /t = O(2 t /t) = O(log n / log log n) \n

\n\n

我们总共有T(n) \xe2\x88\x88 \xce\xa9(log n / log log n)和T(n) \xe2\x88\x88 O(log n/ log log n)，
\nsoT(n) \xe2\x88\x88 \xce\x98(log n/ log log n)成立。您的示例数据也支持此结果。

\n\n

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

\n