【算法导论4-3 i】T(n)=T(n-2)+1/lg n 的渐近界与对数积分
Published:
对 \(T(n)=T(n-2)+1/\lg n\)，给出 \(T(n)\) 的渐近上界和下界。
递推可以得到，
\[T\left(n\right)=\left\{\begin{array}{l l}{{T(2)+\sum\limits_{i=2}^{n/2}\dfrac{1}{\lg 2i}}}&{\text{当 }{n}\text{ 为偶数}}\\ {T(1)+\sum\limits_{i=1}^{(n-1)/2}\dfrac{1}{\lg (2i+1)}}&{\text{当 }{n}\text{ 为奇数}} \end{array}\right.\]难点在于求 \(\sum\limits_{i=2}^{n/2}\dfrac{1}{\lg 2i}\) 和 \(\sum\limits_{i=1}^{(n-1)/2}\dfrac{1}{\lg (2i+1)}\)。先给出 \(n\) 为偶数情况下的讨论。
考虑如上的图示，底边组成 \([1,n/2]\) 的阴影矩形的面积之和即为 \(\sum\limits_{i=2}^{n/2}\dfrac{1}{\lg 2i}\)，或者可以表示为 \(\displaystyle{\int_1^{n/2}\dfrac{\mathrm{d}x}{\lg 2\lceil x\rceil}}\)，其中被积分函数 \(g(x)=\dfrac{1}{\lg 2\lceil x\rceil}\) 的图线就是所有长方形顶边组成的阶梯。下面考虑使用大 \(O\) 表示法将该函数表示为可积的形式。
考虑 \(g(x)\) 与 \(f(x)=\dfrac{1}{\lg 2x}\) 之间的“垂直距离”。注意到 \(f(x)\) 在 \((1/2,\infty)\) 上单调递减，故在区间 \([j,j+1)\) 上有
\[\max (f(x)-g(x))=f(j)-g(j)=\dfrac{1}{\lg 2j}-\dfrac{1}{\lg 2(j+1)}=\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)},\]或者说对 \(\forall\,x\in[j,j+1)\)，\(f(x)-g(x)=O(\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)})\)，其中 \(j=1,2,\dots,n/2-1\)。
这就引出了
\[\begin{aligned} \sum\limits_{i=2}^{n/2}\dfrac{1}{\lg 2i}&=\int_1^{n/2}\dfrac{1}{\lg 2x}-O(\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)})\,\mathrm{d}x\\ &=\int_1^{n/2}\dfrac{\mathrm{d}x}{\lg 2x}-O\big(\int_1^{n/2}\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)}\,\mathrm{d}x\big)\\ &=\dfrac{\ln 2}{2}\mathrm{li}(2x)\bigg|_1^{n/2}-O(\dfrac{1}{\lg 2}-\dfrac{1}{\lg n})\\ &=\dfrac{\ln 2}{2}\mathrm{li}(n)-\dfrac{\ln 2}{2}\mathrm{li}(2)+O(\dfrac{1}{\lg n})\\ &=\Theta(\dfrac{n}{\lg n})+\Theta(1)+O(\dfrac{1}{\lg n})=\Theta(\dfrac{n}{\lg n}). \end{aligned}\]不难注意到，\(\displaystyle{O\big(\int_1^{n/2}\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)}\,\mathrm{d}x\big)}\) 所代表的实际上就是 \(f(x)\) 与 \(g(x)\) 所夹白色区域面积之和，而 \(\displaystyle{\int_1^{n/2}\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)}\,\mathrm{d}x}\) 恰好是所有白色区域左边界的长度之和，即 \(f(1)-f(\dfrac{n}{2})=\dfrac{1}{\lg 2}-\dfrac{1}{\lg n}\)。当然，也可将其分解为在每个子区间 \([j,j+1)\) 上求积分：\(\displaystyle{\int_j^{j+1}\dfrac{1}{\lg 2\lfloor x\rfloor}-\dfrac{1}{\lg 2(\lfloor x\rfloor+1)}\,\mathrm{d}x}=\dfrac{1}{\lg 2j}-\dfrac{1}{\lg 2(j+1)}\)，\(j=1,2,\dots,n/2-1\)。
下面介绍对数积分函数 \(\mathrm{li}(x)\) 并说明 \(\mathrm{li}(n)=\Theta(\dfrac{n}{\lg n})\)。
对所有正实数 \(x\neq 1\)，定义 \(\displaystyle{\mathrm{li}(x)=\int_0^x\dfrac{\mathrm{d}t}{\ln t}}\)。由于 \(\lim\limits_{x\to 1}\mathrm{li}(x)=-\infty\)，当 \(x>1\) 时，该积分只能以第二类反常积分解释，即 \(\displaystyle \mathrm{li}(x)=\lim _{\varepsilon \to 0}\left(\int _{0}^{1-\varepsilon }{\frac {dt}{\ln(t)}}+\int _{1+\varepsilon }^{x}{\frac {dt}{\ln(t)}}\right)\)。下面给出 \(\mathrm{li}(x)\) 的图像，可见，函数在 \((1,\infty)\) 上是单调递增的。
\(\mathrm{li}(x)\) 的渐近展开式为 \(\mathrm{li}(x)=\dfrac {x}{\ln x}\sum\limits_{k=0}^{\infty}\dfrac{k!}{(\ln x)^k}\)（该级数是发散的）。维基百科给出了 \(\mathrm{li}(x)\) 的渐近上界：\(\mathrm{li}(x)=O(\dfrac{x}{\ln x})\)。实际上，我们很容易证明 \(\dfrac{x}{\ln x}\) 也是 \(\mathrm{li}(x)\)的渐近下界。下面给出 \(\mathrm{li}(x)=\Theta(\dfrac{x}{\ln x})\)的证明。
- 下证 \(\exists\,x_1>0\)，当 \(x\ge x_1\) 时，\(\mathrm{li}(x)\le \dfrac{2x}{\ln x}\) 总成立。记 \(h_1(x)=\dfrac{2x}{\ln x}-\mathrm{li}(x)\)，则当 \(x>e^2\) 时，\(\dfrac{\mathrm{d}h_1(x)}{\mathrm{d}x}=\dfrac{\ln x-2}{(\ln x)^2}>0\) 。而 \(h_1(e^2)\approx 2.435>0\)，故当 \(x\ge 8\) 时，\(h_1(x)\ge 0\,\Leftrightarrow\,\mathrm{li}(x)\le \dfrac{2x}{\ln x}\) 成立，\(\mathrm{li}(x)=O(\dfrac{x}{\ln x})\)。事实上，\(\forall\, c_1>1\)，对足够大的 \(x\)，\(\mathrm{li}(x)\le \dfrac{c_1 x}{\ln x}\) 总能成立。
- 下证 \(\exists\,x_2>0\)，当 \(x\ge x_2\) 时，\(\mathrm{li}(x)\ge \dfrac{x}{2\ln x}\ge 0\) 总成立。记 \(h_2(x)=2\,\mathrm{li}(x)-\dfrac{x}{\ln x}\)，则当 \(x>1\) 时，\(\dfrac{\mathrm{d}h_1(x)}{\mathrm{d}x}=\dfrac{1}{\ln x}+\)\(\dfrac{1}{(\ln x)^2}>0\) 。而 \(h_2(3)\approx 1.596>0\)，故当 \(x\ge 3\) 时，\(h_2(x)\ge 0\,\Leftrightarrow\,\mathrm{li}(x)\ge \dfrac{x}{2\ln x}\) 成立，\(\mathrm{li}(x)=\Omega(\dfrac{x}{\ln x})\)。事实上，\(\forall\,0<c_2\le 1\)，只需 \(x\ge 4\)，\(\mathrm{li(x)}\ge \dfrac{c_2 x}{\ln x}\) 就总能成立。
综上，\(\mathrm{li}(x)=\Theta(\dfrac{x}{\ln x})\) 证毕。回到求 \(T(n)\) 渐近界的问题，由 \(\mathrm{li}(n)=\Theta(\dfrac{n}{\lg n})\) 可知，
\[T(n)=T(2)+\sum\limits_{i=2}^{n/2}\dfrac{1}{\lg 2i}=\Theta(1)+\Theta(\dfrac{n}{\lg n})=\Theta(\dfrac{n}{\lg n}).\]我们已经求得了 \(n\) 为偶数情况下，\(T(n)\) 的渐近界。采取类似方法，下面证明 \(n\) 为奇数时亦有 \(T(n)=\Theta(\dfrac{n}{\lg n})\)。
要证：\(\sum\limits_{i=1}^{(n-1)/2}\dfrac{1}{\lg (2i+1)}=\Theta(\dfrac{n}{\lg n})\)。在讨论 \(n\) 为偶数的情况时，我们从线段 \(x=i,y\in[0,f(i)]\,(i=2,3,\dots,n/2)\) 向左作宽为 1 的矩形。然而，注意到 \(\lim\limits_{x\to 0^+}\dfrac{1}{\lg(2x+1)}=+\infty\)，如果效仿这种做法，我们发现在区间 \([0,1)\) 上对 \(p(x)=\dfrac{1}{\lg(2x+1)}\) 积分得到无穷。因此，对于 \(n\) 为奇数的情况，我们采取从 \(x=i,y\in[0,p(i)]\,(i=1,2,\dots,\dfrac{n-1}{2})\) 向右作矩形，于是有
其中第四步用到的 \(\mathrm{li}(n+2)=\Theta(\mathrm{li}(n))\) 和 \(\dfrac{1}{\lg(n+2)}=\Theta(\dfrac{1}{\lg(n)})\) 用代入法易证。到此，对任意 \(n\) 证得 \(T(n)=\Theta(\dfrac{n}{\lg n})\)。
注记：
根据上述两种情况讨论中用到的策略，有如下不等式：
\[\int_{m}^{n+1}f(x)\mathrm{d}x\le \sum_{i=m}^n f(i)\le \int_{m-1}^{n}f(x)\mathrm{d}x,\]其中 \(0<m<n\)，\(f(x)\) 在 \([k-1,n+1]\) 上可积、非负且单调递减。（若 \(f(x)\) 单调递增，则将所有“\(\le\)”换成“\(\ge\)”）
于是，我们也可以使用该不等式对原问题进行求解，以 \(n\) 为偶数情况为例，分别求出渐近下界和渐近上界：
\[\dfrac{\ln 2}{2}(\mathrm{li}(n+2)-\mathrm{li}(4))=\int_2^{n/2+1}\dfrac{\mathrm{d}x}{\lg 2x}\le \sum_{i=2}^{n/2}\dfrac{1}{\lg 2i}\le \int_1^{n/2}\dfrac{\mathrm{d}x}{\lg 2x}=\dfrac{\ln 2}{2}(\mathrm{li}(n)-\mathrm{li}(2)).\]这也表明 \(\sum\limits_{i=2}^{n/2}\dfrac{1}{\lg 2i}=\Theta(\mathrm{li}(n))=\Theta(\dfrac{n}{\lg n})\)。
对数积分 \(\mathrm{li}(x)\) 与其他特殊函数的关系：
- 欧拉对数积分 \(\displaystyle \mathrm{Li}(x)=\int_2^x\dfrac{\mathrm{d}t}{\ln t}=\mathrm{li}(x)-\mathrm{li}(2)\) 规避了 \(\mathrm{li}(x)\) 的不连续点，有时可在相似情况下替代 \(\mathrm{li}(x)\)。对数积分在数论中有重要的应用，例如素数定理表明，对正实数 \(x\)，不大于 \(x\) 的素数个数为 \(\pi(x)=\mathrm{Li}(x)+O(xe^{-{\frac{1}{15}}\sqrt{\ln x}})\)。
- \(\mathrm{li}(x)\) 与指数积分 \(\displaystyle \mathrm{Ei}(x)=\int_{-\infty}^x\dfrac{e^t}{t}\mathrm{d}t\) 有如下关系：\(\mathrm{li}(x)=\mathrm{Ei}(\ln x), x\ne1\)。
借助可视化往往对渐近界类问题的分析有较大帮助，GeoGebra 提供了一款强大的在线图形计算器。