算法导论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$$

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

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