4.3-1
用數學歸納法證明即可，思路是假設$n<=k$時存在c使得$T(k)<=c{n}^2$成立，只要證明出$n=k+1$時，存在c使得$T(k+1)<=c(k+1{)}^2$。那么把$T(k)和T(k?1)$代入遞歸式得到：
$$\begin{array}{rl}T(k)& =T(k?1)+k\\ & <=c?(k?1{)}^2+k\\ & =c(k^2?2k+1)+k\end{array}$$
把T(k)的方程代入T(k+1)的方程可以得到：
$$\begin{array}{rl}T(k+1)& =T(k)+k+1\\ & <=c(k^2?2k+1)+k+k+1\\ & =c(k^2?2k+1+\frac{2k+1}{c})\end{array}$$
當$c=\frac{1}{2}+\frac{1}{4k}$時，k無窮大時$c=\frac{1}{2}$，即$c>\frac{1}{2}$.代入上式可得：
$$T(k+1)<=c(k+1{)}^2,c>\frac{1}{2}$$
證明完畢。

4.3-2

用書中所介紹的代入法計算可能會更簡單一些：假設對于m$(m<n)$成立。令:
$$m=?\frac{n}{2}?$$
即對于m，滿足方程的解為$O(lgn),即T(m)<=c?lgm$,將其代入n的遞歸式中，解出使方程成立的c的解即可。
$$\begin{array}{rl}T(n)& <=c?\lg ?\frac{n}{2}?+1\\ & <=c?\lg (\frac{n}{2}+1)+1\\ & <=c?\lg (n+2)?c?\lg (2)+1\end{array}$$
顯然不成立,因為lg(n+2)>lg(n),按照書中的方法，令n減去d重新計算，猜測：$T(n)<=c?lg(n?2)$,證明方法和上文中的一樣
$$\begin{array}{rl}T(n)& <=c?\lg (?\frac{n}{2}??2)+1\\ & <=c?\lg (\frac{n}{2}+1?2)+1\\ & =c?\lg ((n?2)/2)+1\\ & =c?\lg (n?2)?c+1\end{array}$$
在c大于1時，上式成立，且lg(n-2)<lgn。對于漸進上界O(lgn)來說，原式成立。

4.3-3
根據題意，只需證明$T(n)>=c?n\lg (n)$,和上一題類似依舊用代入法證明，假設在m<n時$T(m)$成立，只需證明在n處，有$T(n)>=cnlg(n)$即可。先將
$$m=?\frac{n}{2}?$$
代入原式中，得：
$$\begin{array}{rl}T(n)& >=2c?\frac{n}{2}?\lg ?\frac{n}{2}?+n\\ & >=2c(\frac{n}{2}?1)\lg (\frac{n}{2}?1)+n\\ & =c(n?2)(\lg (n?2)?1)+n\end{array}$$
很顯然沒有得到我們想要的結果，由于是在證明T(n)>=cnlg(n)時,選擇在后面加上一個常數項。
即假設$T(n)>=c(n+2)lg(n+2)$,證明如下：
$$\begin{array}{rl}T(n)& >=2c(?\frac{n}{2}?+2)(\lg (?\frac{n}{2}?+2)+n\\ & >=c(n+2)\lg (\frac{n+2}{2})+n\\ & =c(n+2)\lg (n+2)+(1?c)n?2c\\ & >=c(n+2)\lg (n+2)\end{array}$$
在$0<=c<1且n>=\frac{2c}{1?c}$的時候上式最后一步成立，且$(n+2)lg(n+2)>nlgn$,所以證明完畢。

4.3-4

要想不調整歸納證明中的邊界條件，只能放大漸進上界，比如求其解為$T(n)=O(nlgn+n)$
歸納證明的方法和前面的類似，此時把邊界條件$n=1$代入，$T(1)=1lg1+1=1$,所以不需要調整遞歸邊界條件。

4.3-5

4.3-6

這個和前面類似，直接證也是證明不出來的，需要減去一個常數項，即證明：
$$T(n)<=c(n?36)\lg (n?36)$$
證明方式和前面一模一樣。

4.3-7

總結

以上是生活随笔為你收集整理的＜算法导论＞练习4.3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。