4.5-1

a) $$a=2,b=4,f(n)=\Theta(1),\log_b a = \frac 12 \gt 0 $$ 符合情況1，$ T(n) = \Theta (n^{1/2})$

b) $$a=2,b=4,f(n)=\Theta(n^{1/2}),\log_b a = \frac 12 $$ 符合情況2，$ T(n) = \Theta (n^{1/2}\lg n)$

c) $$a=2, b=4, f(n)=\Theta(n),\log_b a = \frac 12$$ $$af(\frac nb) = 2f(\frac n4) = \frac n2 \le cf(n) \qquad (\frac 12 \le c \lt 1)$$ 符合情況3，$ T(n) = \Theta (n)$

d) $$a=2, b=4, f(n)=\Theta(n^2),\log_b a = \frac 12$$ $$af(\frac nb) = 2f(\frac n4) = \frac {n^2}2 \le cf(n) \qquad (\frac 12 \le c \lt 1)$$ 符合情況3，$ T(n) = \Theta (n^2)$

4.5-2
同4.2-4

• 如果$\log_4 a =2 \ \Rightarrow \ k=16$，那么滿足第2種情況，$T(n)=\Theta (n^2 \lg n)=o(n^{\lg 7})$
• 如果$\log_4 a \lt 2 \ \Rightarrow \ k \lt 16$，那么滿足第1種情況，$T(n)= \Theta (n^2)=o(n^{\lg 7})$
• 如果$\log_4 a \gt 2 \ \Rightarrow \ k \gt 16$，那么滿足第3種情況，這時(shí)$\log_4 a \lt \lg 7 \Rightarrow a \lt 4^{\lg 7} = 49$

所以最大的a為48。

4.5-3
$$a=1, b=2, f(n)=\Theta(1),\log_b a = 0$$ 符合情況2，$ T(n) = \Theta (\lg n)$

4.5-4
$$a=4, b=2, \log_b a = 2, f(n)=\Omega (n^2)$$ 但不存在$\epsilon \gt 0$，使得 $$f(n) = \Omega (n^{2+\epsilon})$$ 所以不能使用主方法(master method)來求解。可以利用遞歸樹來估計(jì) $$\eqalign { T(n) & = \sum_{i=0}^{\lg n-1}n^2(\lg n-i) + \Theta (n^2) \\ & = n^2 \lg^2n-n^2\lg n -\frac 12 n^2 \lg^2 n + \frac 12 n^2 \lg n + \Theta (n^2) \\ & = \frac 12 n^2 \lg^2 n - n^2 \lg n + \Theta (n^2) \\ & = O(n^2\lg^2 n)}$$

4.5-5
不會(huì)，求指教

4-1

a) $$a=2,b=2, f(n)= n^4=\Omega (n^{\log_2 2+3})$$ $$af(\frac nb) = 2 (\frac n2)^4 = \frac 18 n^4 \le cf(n) \qquad (\frac 18 \le c \lt 1)$$ 滿足情況3，所以$T(n)=\Theta(n^4)$

b) $$a=1, b=\frac {10}{7}, f(n)=n=\Omega(n^{\log_{10/7}{1}+1}) \\ af(\frac nb)=\frac {7n}{10} \le cf(n) \qquad (\frac {7}{10} \le c \lt 1)$$ 滿足情況3，所以$T(n)=\Theta(n)$

c) $$a=16, b=4, f(n)=n^2=\Theta(n^{\log_{4}{16}})$$ 滿足情況2，所以$T(n)=\Theta(n^2 \lg n)$

d) $$a=7, b=3, f(n)=n^2=\Omega(n^{\log_37+\epsilon}) \qquad (0 \lt \epsilon \le 2-\log_37) \\ af(\frac nb)=7(\frac {n}{3})^2 \le cf(n) \qquad (\frac 79 \le c \lt 1)$$ 滿足情況3，所以$T(n)=\Theta(n^2)$

e) $$a=7, b=2, f(n)=n^2=O(n^{\log_{2}{7}-\epsilon}) \qquad (0 \lt \epsilon \le \log_2 7 - 2)$$ 滿足情況1，所以$T(n)=\Theta(n^{\lg 7})$

f) $$a=2, b=4, f(n)=\sqrt n=\Theta(n^{\log_{4}{2}})$$ 滿足情況2，所以$T(n)=\Theta(\sqrt n \lg n)$

g) 利用遞歸樹可以看出第i層的規(guī)模為n-2i，所以總時(shí)間為 $$T(n) = \sum_{i=0}^{n/2-1} {(n-2i)^2} = \frac {n(n+1)}2=\Theta(n^3)$$ 證明：假定有$\forall m < n, T(m) \le c \lg m^3$，代入遞推式可得 $$\eqalign { T(n) & \le c(n-2)^3+n^2 \\ & = c(n^3-6n^2+12n-8) + n^2 \\ & \le cn^3-(6c-1-12c\frac1n)n^2 \\ & \le cn^3 -(6c-1-4c)n^2 &(n \ge 3) \\ & \le cn^3 & (c\ge \frac 12)}$$

4-2

a)

• 方法1的時(shí)間遞推式為$T(n)=T(n/2)+\Theta(1)$，可以得出$T(n)=O(\lg n)$
• 方法2的時(shí)間遞推式為$T(n)=T(n/2)+\Theta(n)$，可以得出$T(n)=O(n)$
• 方法3的時(shí)間遞推式為$T(n)=T(n/2)+\Theta(N)$，可以得出$T(n)=O(n\lg n)$

b)

• 方法1的時(shí)間遞推式為$T(n)=2T(n/2)+\Theta(n)$，可以得出$T(n)=O(n \lg n)$
• 方法2的時(shí)間遞推式為$T(n)=2T(n/2)+\Theta(n)$，可以得出$T(n)=O(n \lg n)$
• 方法3的時(shí)間遞推式為$T(n)=2T(n/2)+\Theta(N)$，可以得出$T(n)=O(n^2)$

4-3

a) $$a=4, b=3, f(n)=O(n^{\log_34 - \epsilon}) \qquad (0 \lt \epsilon \lt \log_34 -1))$$ 滿足情況1，所以$T(n)=\Theta(n^{\log_34})$

b) $a=3, b=3, f(n)=o(n)$，不存在$\epsilon \gt 0$，使得$f(n) = O(n^{\log_33 -\epsilon})$，所以不能使用主方法。
利用遞歸樹來求解，第i層的時(shí)間為$n/\lg { (n/{3^i})}$，層數(shù)為$\log_3 n$，最底層時(shí)間為$3^{\log_3 n}=n$，可得總時(shí)間為 $$\eqalign { T(n) & = \sum_{i=0}^{log_3 n - 1} \frac n {\lg {(n/3^i)}} \\ & = n\sum_{i=0}^{\log_3 n -1}{\frac 1{\lg n - i\lg 3}} \\ & = n\sum_{i=0}^{\log_3 n -1}{\frac 1{1 + i\lg3}}}$$ 令$$a_i = \frac {1}{1+i\lg3}, S_n = \sum_{i=1}^{n} a_i$$ $$\because \frac {1}{(i+1)\lg 3} \lt a_i \lt \frac {1}{i\lg 3}$$ $$\therefore \frac 1{\lg 3}\ln {(n+1)} + C_1 \lt S_n \lt \frac 1{\lg3}\ln n+C_2$$ 可以得到$$\Rightarrow \cases {T(n) \lt \frac 1{\lg 3}n\ln {\log_3 n}+\Theta(n)=O(n\lg {\lg n}) \\ T(n) \gt \frac 1{\lg3}n \ln (\log_3 n+1) + \Theta(n)=\Omega(n\lg {\lg n})}$$ 所以$T(n) = \Theta (n \lg {\lg n})$

c) $$a=4, b=2, f(n)=n^{2.5}=\Omega (n^{\log_2 4 + 0.5})$$ $$af(\frac nb) = 4(\frac n2)^{2.5}=\frac 1{\sqrt 2}n \lt cf(n) \qquad (\frac 1{\sqrt 2} \le c \lt 1)$$ 滿足情況3，所以$T(n)=\Theta(n^2 \sqrt n)$

d) 通過遞歸樹可得第0層規(guī)模為n，第1層為n-2 \times 3，第2層為n-2 \times 3 - 2 \times 3^2，層數(shù)區(qū)間為$[\log_3 n - 1, \log_3 n]$所以總時(shí)間為 $$\eqalign { T(n) & \le \frac12 \sum_{i=0}^{\log_3 n - 2} {(n-2\sum_{j=1}^{i}{3^j})} + \Theta(n) \\ & = \frac 12 n\log_3n - \sum_{i=1}^{\log_3 n - 1}{\frac {3^{i+1}-1}{2}}+ \Theta(n) \\ & \lt \frac 12 n \log_3 n - \frac 32 n+ \Theta(n) \\ & = O(n \lg n) }$$ $$\eqalign { T(n) & \ge \frac12 \sum_{i=0}^{\log_3 n - 2} {(n-2\sum_{j=1}^{i}{3^j})} + \Theta(n) \\ & = \frac 12 n(\log_3n-1) - \sum_{i=1}^{\log_3 n - 1}{\frac {3^{i+1}-1}{2}}+ \Theta(n) \\ & \gt \frac 12 n \log_3 n - \frac 32 n+ \log_3 n + \Theta(n) \\ & = \Omega(n \lg n) }$$ 證明：假定有$\forall m \lt n, T(m) \le cm \lg m$，代入遞推式可得 $$\eqalign {T(n) & \le 3c(\frac n3-2) \lg {(\frac n3-2)} + \frac n2 \\ & \lt 3c\frac n3 \lg {\frac n3} + \frac n2 \\ & = cn\lg n - (c\lg3 - \frac 12)n \\ & \le cn\lg n & (c \ge \frac 1{2 \lg 3}) }$$ 假定有$\forall m \lt n, T(m) \ge c(m+d) \log_3 (m+d)$，代入遞推式可得 $$\eqalign {T(n) & \ge 3c (\frac n3 -2 +d) \log_3 {(\frac n3 -2 +d)}+\frac n2 \\ & = 3c(\frac n3+d-2) (\log_3 (n-6+3d) -1)+\frac n2 \\ & = cn\log_3 {(n-6+3d)}+(\frac 12-c)n+3c(d-1)\log_3 {(n-6+3d)+3c(d-1)} \\ & \ge cn\log_3 {(n+d)}}$$ 其中$2d-6 \ge 0,\frac12 -c \ge 0, d-1 \ge 0 \Rightarrow 0 \lt c \le \frac 12, d \ge 3$

e) 同b)，$T(n)=n \lg {\lg n}$

f) 根據(jù)遞歸樹可知第i層的規(guī)模為$(\frac 78)^in$，最長路徑為$\lg n$，最短路徑為$\log_8 n$，所以 $$\eqalign {T(n) & \lt \sum_{i=0}^{\lg n-1}{(\frac 78)^in} \\ & = \frac {1-(7/8)^{\lg n}}{1-(7/8)} n \\ & = 8(n-n^{1+\lg {(7/8)}}) \\ & = O(n)}$$ $$\eqalign {T(n) & \gt \sum_{i=0}^{\log_8 n-1}{(\frac 78)^in} \\ & = \frac {1-(7/8)^{\log_8 n}}{1-(7/8)} n \\ & = 8(n-n^{1+\log_8 {(7/8)}}) \\ & = \Omega(n)}$$ 證明：假定有$\forall m \lt n, T(m) \le cm$，代入遞推式可得 $$\eqalign {T(n) & \le c\frac n2 +c\frac n4 + c\frac n8 +n \\ & = cn - (\frac 18c-1)n \\ & \le cn & (c \ge 8)}$$ 假定有$\forall m \gt n, T(m) \le cm$，代入遞推式可得 $$\eqalign {T(n) & \ge c\frac n2 +c\frac n4 + c\frac n8 +n \\ & = cn + (1-\frac 18c)n \\ & \ge cn & (c \le 8)}$$

g) 根據(jù)遞歸樹可知，第i層的規(guī)模為$n-i$，層數(shù)為n，總時(shí)間為 $$T(n) = \sum_{i=0}^{n-1} {\frac 1{n-i}} = \sum_{i=1}^{n} {\frac 1i} = \ln n + C=\Theta(\lg n)$$

h) 根據(jù)遞歸樹可知，第i層的規(guī)模為$n-i$，層數(shù)為n，總時(shí)間為 $$T(n) = \sum_{i=0}^{n-1} {\lg (n-i)} = \sum_{i=1}^{n} {\lg i} = \lg {(n!)} = \Theta (n \lg n)$$

i) 根據(jù)遞歸樹可知，第i層的規(guī)模為$n-2i$，層數(shù)為$n/2$，總時(shí)間為 $$\eqalign {T(n) & = \sum_{i=0}^{n/2-1}{\frac 1{\lg {(n-2i)}}} = \sum_{i=2}^{n/2}{\frac 1{1 + \lg i}} }$$ 令 $$a_i = \frac 1{1+\lg i}, S_n = \sum_{i=2}^{n}{a_i} $$ $$\because \frac 1{2\lg i} \le a_i \lt \frac 1{\lg i}$$ $$\sum_{i=2}^{n} \dfrac1{\lg i} \sim \int_2^n \dfrac{dx}{\lg x} \sim \dfrac{n}{\lg n}$$ $$\therefore S_n \sim \frac n{\lg n}$$ 所以可知$T(n) = \Theta(n/ \lg n)$

j) 根據(jù)遞歸樹可知，每層的規(guī)模都是n，層數(shù)為$\lg {\lg n}$，所以總時(shí)間為 $$T(n) = n \lg {\lg n} = \Theta (n \lg {\lg n})$$

4-4

a) $$\eqalign { & \quad \mathcal{z + zF(z) + z^2F(z)} \\ & = z + z \sum_{i=0}^{\infty}{F_iz^i} + z^2 \sum_{i=0}^{\infty}{F_iz^i} \\ & = z + \sum_{i=0}^{\infty}{F_iz^{i+1}} + \sum_{i=0}^{\infty}{F_iz^{i+2}} \\ & = z + \sum_{i=2}^{\infty}{(F_{i-2} + F_{i-1})z^i} \\ & = 0 + z + \sum_{i=2}^{\infty}{F_iz^i} \\ & = \mathcal{F(z)}}$$

b) 根據(jù)a)的結(jié)論，解$\mathcal{F(z)}$關(guān)于$z$的方程即可得到 $$\mathcal{F(z)} = \frac z{1-z-z^2}$$

c) 根據(jù)斐波那契數(shù)列(Fibonacci numbers)通項(xiàng) $$F_i = \frac {\phi ^i-\hat{\phi}^i}{\sqrt 5}$$ 可得 $$\sum_{i=0}^{n}{F_iz^i} = \sum_{i=0}^{n} {\frac {\phi ^i-\hat{\phi}^i}{\sqrt 5}z^i}$$

d) 由于 $$F_i = \frac {\phi ^i-\hat{\phi}^i}{\sqrt 5} \\ \Rightarrow \frac {\phi ^i} {\sqrt 5} = F_i - \frac {\hat {\phi}^i}{\sqrt 5}$$ $$\because \frac {\hat {\phi}^i}{\sqrt 5} \lt 0.5 \\ \therefore F_i = \frac {\phi ^i}{\sqrt 5} \pm c \qquad (0 \lt c \lt 0.5)$$ 得證。

4-5

a) 由于有一半以上是壞的零件，所以假定現(xiàn)在一共有三個(gè)零件，那么其中至少有兩個(gè)是壞的。假如每個(gè)壞的零件在測試別的零件的時(shí)候都說是壞的，那么沒有一個(gè)零件會(huì)說對(duì)方是好的，由于所有的結(jié)果都一樣，所以無法判斷到底哪個(gè)是好的零件。

b) 假如現(xiàn)在有k個(gè)零件，將他們兩兩一組進(jìn)行測試，然后將出現(xiàn)第一種情況（互相說對(duì)方是好的）的零件取任意一個(gè)留下，另一個(gè)舍棄，其他情況的都不留下。如果零件的數(shù)量是奇數(shù)，那么沒有配對(duì)的零件也留下。然后對(duì)剩下的零件重復(fù)以上操作，直至只剩一個(gè)零件，該零件為所求。
分析：一組出現(xiàn)的情況有三種：2個(gè)好零件、1好1壞、2個(gè)壞零件。假設(shè)：

• 2個(gè)好零件有x組
• 1好1壞有y組
• 2個(gè)壞零件有z組
• 共有g(shù)個(gè)好零件，b個(gè)壞零件

那么：

• 如果k是偶數(shù)，那么$g=2x+y \gt b = y + 2z \Rightarrow x \gt z$，這種情況下x個(gè)好零件和z個(gè)壞零件留下了，剩下的數(shù)量$x+z \le (2x+2y+2z)/2$
• 如果k是奇數(shù)，且多余的零件是壞的，那么$g=2x+y \gt b = y + 2z + 1 \Rightarrow x \gt z + 1$，這種情況有x個(gè)好零件和z+1個(gè)壞零件留下了，剩下的數(shù)量$x+z+1 \le \lceil (2x+2y+2z+1)/2 \rceil$
• 如果k是奇數(shù)，且多余的零件是好的，那么$g=2x+y+1 \gt b = y + 2z \Rightarrow x+1 \gt z$，這種情況有x+1個(gè)好零件和z個(gè)壞零件留下了，剩下的數(shù)量$x+z+1 \le \lceil (2x+2y+2z+1)/2 \rceil$

所以，不管什么情況下剩余的好零件都多于壞零件，并且總數(shù)量不大于原來的一半，共需$\lfloor k/2 \rfloor$次比較。

c) 當(dāng)找到一個(gè)好零件之后只要用它測試其他的零件即可找出其他的好零件。找出一個(gè)好零件的時(shí)間$T_1(n)=T_1(n/2)+O(n)＝O(n)$，找出其他好零件的時(shí)間$T_2(n) = n-1 = O (n)$，所以總的時(shí)間$T(n)= O(n)$。

4-6

a) 令$k=i+1,l=j+1$顯然當(dāng) $$A[i,j]+A[k,l] \le A[i,l] + A[k,j]$$ 時(shí)有 $$A[i,j]+A[i+1, j+1] \le A[i+1, j] + A[i, j+1]$$ 接下來證另一個(gè)方向。 假設(shè)對(duì)于$x' \lt m, y' \lt n$，有： $$\forall 1 \le x \le x', 1 \le y \le y', \quad A[i, j]+A[i+x,j+y] \le A[i+x,j] + A[i, j+y]$$ 于是要證對(duì)于$x=x'+1, y=y'$也成立。根據(jù)假設(shè)，可知： $$A[i, j] + A[i+x', j+ y'] \le A[i+ x', j] + A[i, j+y'] \tag {1}$$ 同時(shí)有： $$\forall 1 \le k \le y', \quad A[i+x', j+k-1] + A[i+x'+1, j+k] \le A[i+x'+1, j+k-1] + A[i+x', j+k]$$ $$\Rightarrow A[i+x', j] + A[i+x'+1, j+y'] \le A[i+x'+1, j] + A[i+x', j+y'] \tag {2}$$ 式(1)+式(2)： $$A[i, j] + A[i+x', j+ y'] + A[i+x', j] + A[i+x'+1, j+y'] \\ \le A[i+ x', j] + A[i, j+y'] + A[i+x'+1, j] + A[i+x', j+y'] $$ $$\Rightarrow A[i, j] + A[i+x'+1, j+y'] \le A[i+x'+1, j] + A[i+x', j+y']$$ 得證。同理可證對(duì)于$x=x', y=y+1'$也成立。

b) 改動(dòng)紅色的元素 $$\begin {pmatrix} 37 & 23 & 22 & 32 \\ 21 & 6 & {\color {red} 5} & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \end {pmatrix}$$

c) 假設(shè)$\exists i, f(i) \gt f(i+1)$，那么有 $$A[i, f(i)] \gt A[i+1, f(i+1)]$$ $$\Rightarrow A[i, f(i+1)] + A[i+1, f(i)] \gt A[i, f(i)] + A[i+1, f(i+1)]$$ 與蒙赫陣列(Monge array)的定義矛盾，所以得證。

d) 由于我們已經(jīng)知道偶數(shù)行最小值的位置，根據(jù)c)的結(jié)論可知，對(duì)于奇數(shù)行2k+1，$f(2k) \le f(2k+1) \le f(2k+2)$，所以只要求該區(qū)間元素的最小值即可。 $$T(n) = \sum_{i=1}^{m/2} {(f(2k) - f(2k-2)+1)}\le m+n = O(m+n)$$

e) 每次迭代行數(shù)減半，所以$T(m) = T(m/2) + O(m+n)$ $$T(n) = \sum_{i=0}^{\lg m-1}{(\frac m{2^i}+n)} \le 2m + n\lg m = O(m+ n\lg m)$$

轉(zhuǎn)載于:https://www.cnblogs.com/Jiajun/archive/2013/05/10/3071337.html

總結(jié)

以上是生活随笔為你收集整理的算法导论课后习题解析 第四章 下的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。