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