算法导论A.2 Exercises 答案

A.2-1

\[\begin{aligned} \sum_{k=1}^n\dfrac{1}{k^2}&=1+\sum_{k=2}^n\dfrac{1}{k^2} \\ &\le 1+\sum_{k=2}^n\dfrac{1}{k(k-1)}\\ &= 1+\sum_{k=2}^n\left(\dfrac{1}{k-1}-\dfrac{1}{k}\right)\\ &=1+1-\dfrac{1}{n}\\ &<2 \end{aligned}\]

因此这个求和式有常数上界\(2\)。

A.2-2

如果\(n=2^m\)，并且\(n\)恰好是\(2\)次幂，那么有

\[\sum_{k=0}^{\lfloor\lg n\rfloor} \left\lceil\dfrac{n}{2^k}\right\rceil=\sum_{k=0}^{m} \dfrac{n}{2^k}=\sum_{k=0}^m 2^k=2n-1\]

那么令\(n'=2^{\lceil\lg n\rceil}\)，可以发现，\(\dfrac{n'}{n}=2^{\lceil\lg n\rceil-\lg n}<2^1=2\)，也就是\(n'<2n\)。

那么有

\[\sum_{k=0}^{\lfloor\lg n\rfloor}\left\lceil\dfrac{n}{2^k}\right\rceil\le\sum_{k=0}^{\lfloor\lg n'\rfloor}\left\lceil\dfrac{n'}{2^k}\right\rceil=2n'-1<4n-1=O(n)\]

A.2-3

对于级数\(\displaystyle{\sum_{k=1}^n \dfrac{1}{k}}\)的值。考虑它前缀的一部分，也就是\(\displaystyle{\sum_{k=1}^{2^{\lfloor\lg n\rfloor-1}} \dfrac{1}{k}}\)，采用推导\((A.17)\)类似的做法，那么有：

\[\begin{aligned} \sum_{k=1}^n\dfrac{1}{k}&>\sum_{k=1}^{2^{\lfloor\lg n\rfloor-1}}\dfrac{1}{k}\\ &=\sum_{i=0}^{\lfloor\lg n\rfloor}\sum_{j=0}^{2^i-1} \dfrac{1}{2^i+j}\\ &>\sum_{i=0}^{\lfloor\lg n\rfloor}\sum_{j=0}^{2^i-1} \dfrac{1}{2^{i+1}}\\ &=\sum_{i=0}^{\lfloor\lg n\rfloor}\dfrac{1}{2}\\ &>\dfrac{1}{2}\lfloor\lg n\rfloor\\ &=\Omega(\lg n) \end{aligned}\]

A.2-4

直接代入\((A.18)\)式进行逼近。

上界：

\[\sum_{n=1}^k k^3\le \int_{1}^{n+1} x^3 dx=\left.\dfrac{x^4}{4}\right|_{1}^{n+1}=\dfrac{(n+1)^4-1}{4}\]

下界：

\[\sum_{n=1}^k k^3\ge \int_{0}^{n} x^3 dx=\left.\dfrac{x^4}{4}\right|_{0}^{n}=\dfrac{n^4}{4}\]

因此最终得到\(\sum_{k=1}^nk^3\)的估计为：

\[\dfrac{n^4}{4}\le \sum_{k=1}^n k^3\le\dfrac{(n+1)^4-1}{4}\]

A.2-5

\(f(x)=\dfrac{1}{x}\)是一个单调递减函数，考虑它的上界：

\[\int_{0}^n \dfrac{1}{x}dx\]

可以发现，这个积分值是无穷大。

因此，用积分法估计调和级数的界限是失败的。