算法导论A Problems 答案

A-1

a

本题做法与A-1.5完全一致。

由于\(f(x)=x^r\)是递增的，因此考虑使用式子\((A.18)\)进行逼近。

上界：

\[\sum_{n=1}^k k^r\le \int_{1}^{n+1} x^r dx=\left.\dfrac{x^{r+1}}{r+1}\right\rvert_{1}^{n+1}=\dfrac{(n+1)^{r+1}}{r+1}-1\]

下界：

\[\sum_{n=1}^k k^r\ge \int_{0}^{n} x^r dx=\left.\dfrac{x^{r+1}}{r+1}\right\rvert_{0}^{n}=\dfrac{n^{r+1}}{r+1}\]

最终可以得到：

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

并且有\(\dfrac{n^{r+1}}{r+1}=\Omega(n^{r+1}),\dfrac{(n+1)^{r+1}}{r+1}-1=O(n^{r+1})\)，因此最终有：

\[\sum_{n=1}^k k^r=\Theta(n^{r+1})\]

b

由于

\(\begin{aligned} \sum_{k=1}^{n} \lg ^s k &= \sum_{k=1}^{n/2} \lg ^s k + \sum_{k= n/2+1}^{n} \lg ^s k\\ &\ge \sum_{k=1}^{n/2} 0 + \sum_{k= n/2+1}^{n} \lg ^s (n/2)\\ &=n/2\cdot\lg ^s(n/2)\\ &=n/2\cdot(\lg n-1)^s\\ &\ge n/2\cdot \left(\dfrac{\lg n}{2}\right)^s &(A)\\ &=\dfrac{1}{2^{s+1}}\cdot n\cdot \lg^sn \end{aligned}\)

其中步骤\((A)\)使用了假设\(n\ge 4\)。因此有\(\displaystyle{\sum_{k=1}^{n} \lg ^s k =\Omega(n\lg^s n)}\)。

又因为

\(\begin{aligned} \sum_{k=1}^{n} \lg ^s k &\le \sum_{k=1}^{n} \lg ^s n\\ &=n\lg^sn \end{aligned}\)

因此有\(\displaystyle{\sum_{k=1}^{n} \lg ^s k =O(n\lg^s n)}\)，最终有\(\displaystyle{\sum_{k=1}^{n} \lg ^s k =\Theta(n\lg^s n)}\)。

c

与题目8-2-b类似，由于

\(\begin{aligned} \sum_{k=1}^{n} k^r\lg ^s k &= \sum_{k=1}^{n/2} k^r\lg ^s k + \sum_{k= n/2+1}^{n} k^r\lg ^s k\\ &\ge \sum_{k=1}^{n/2} 0 + \sum_{k= n/2+1}^{n} (n/2)^r\lg ^s (n/2)\\ &=(n/2)^{r+1}\cdot\lg ^s(n/2)\\ &=(n/2)^{r+1}\cdot(\lg n-1)^s\\ &\ge (n/2)^{r+1}\cdot\left(\dfrac{\lg n}{2}\right)^s &(A)\\ &=\dfrac{1}{2^{r+s+1}} \cdot n^{r+1}\cdot \lg^sn \end{aligned}\)

其中步骤\((A)\)使用了假设\(n\ge 4\)。因此有\(\displaystyle{\sum_{k=1}^{n} k^r\lg ^s k =\Omega(n^{r+1}\lg^s n)}\)。

又因为

\(\begin{aligned} \sum_{k=1}^{n} k^r\lg ^s k &\le \sum_{k=1}^{n} n^r\lg ^s n\\ &=n^{r+1}\lg^sn \end{aligned}\)

因此有\(\displaystyle{\sum_{k=1}^{n}k^r \lg ^s k =O(n^{r+1}\lg^s n)}\)，最终有\(\displaystyle{\sum_{k=1}^{n}k^r \lg ^s k =\Theta(n^{r+1}\lg^s n)}\)。