算法导论4 Problems 答案
4-1
a
\(a=2,b=2,f(n)=n^3,\log _b a=1\)
因此根据第三个条件，可以构造出\(c=\dfrac{1}{8}\)，最终\(T(n)=\Theta(n^3)\)
b
\(a=1,b=\dfrac{11}{8},f(n)=n,\log _b a=0\)
因此根据第三个条件，可以构造出\(c=\dfrac{8}{11}\)，最终\(T(n)=\Theta(n)\)
c
\(a=16,b=4,f(n)=n^2,\log _b a=2\)
因此根据第二个条件，得到\(k=0\)，最终\(T(n)=\Theta(n^2\cdot \lg n)\)
d
\(a=4,b=2,f(n)=n^2\lg n,\log _b a=2\)
因此根据第二个条件，得到\(k=1\)，最终\(T(n)=\Theta(n^2\cdot \lg^2 n)\)
e
\(a=8,b=3,f(n)=n^2,\log _b a=\log_3 8<2\)
因此根据第三个条件，可以构造出\(c=\dfrac{8}{9}\)，最终\(T(n)=\Theta(n^2)\)
f
\(a=7,b=2,f(n)=n^2\lg n,\log _b a=\log_2 7>2\)
因此根据第一个条件，\(T(n)=\Theta(n^{\lg 7})\)
g
\(a=2,b=4,f(n)=\sqrt{n},\log _b a=\log_4 2=\dfrac{1}{2}\)
因此根据第二个条件，得到\(k=0\)，最终\(T(n)=\Theta(\sqrt{n}\cdot \lg n)\)
h
令 \(m=n\bmod 2\)，可以知道，\(m\in\{0,1\}\)。
那么有：
\(\begin{aligned} T(n)&=\sum_{k=0}^{n/2} (2k+m)^2\\ &=\sum_{k=0}^{n/2} (4k^2+4km+m^2)\\ &=\dfrac{m^2n}{2}+\sum_{k=0}^{n/2} (4k^2+4km)\\ &=\dfrac{m^2n}{2}+4\sum_{k=0}^{n/2} k^2+4m\sum_{k=0}^{n/2} k\\ &=\dfrac{m^2n}{2}+4\cdot\dfrac{n/2\cdot(n/2+1)(n+1)}{6} + 4m\cdot\dfrac{n/2\cdot(n/2+1)}{2}\\ &=\Theta(n^3) \end{aligned}\)
4-2
\(\begin{aligned} &T_{a1}(N,n)=T_{a1}(N,n/2)+\Theta(1)\\ &T_{a2}(N,n)=T_{a2}(N,n/2)+\Theta(N)\\ &T_{a3}(N,n)=T_{a3}(N,n/2)+\Theta(n)\\ &T_{b1}(N,n)=2T_{b1}(N,n/2)+\Theta(1)+\Theta(n)\\ &T_{b2}(N,n)=2T_{b2}(N,n/2)+\Theta(N)\\ &T_{b3}(N,n)=2T_{b3}(N,n/2)+\Theta(n)\\ &T_{c1}(N,n)=8T_{c1}(N,n/2)+\Theta(1)\\ &T_{c2}(N,n)=8T_{c2}(N,n/2)+\Theta(N^2)\\ &T_{c3}(N,n)=8T_{c3}(N,n/2)+\Theta(n^2)\\ \end{aligned}\)
\(T_{a1}:a=1,b=2,f(n)=\Theta(1),\log_ba=0\)。因此根据第二个条件，得到\(k=0\)，最终\(T_{a1}(N,n)=\Theta(\lg n)\)。
\(\begin{aligned} T_{a2}(N,n)&=T_{a2}(N,n/2)+\Theta(N)\\ &=T_{a2}(N,n/4)+\Theta(N)+\Theta(N)\\ &=T_{a2}(N,n/8)+\Theta(N)+\Theta(N)+\Theta(N)\\ &\dots\\ &=\sum_{i=0}^{\lfloor\lg n\rfloor-1} \Theta(N)\\ &=\Theta(N\cdot \lg n) \end{aligned}\)
\(T_{a3}:a=1,b=2,f(n)=\Theta(n),\log_ba=0\)。因此根据第三个条件，可以构造出\(c=\dfrac{1}{2}\)，最终\(T_{a3}(N,n)=\Theta(n)\)。
\(T_{b1}:a=2,b=2,f(n)=\Theta(n),\log_ba=1\)。因此根据第二个条件，得到\(k=0\)，最终\(T_{b1}(N,n)=\Theta(n\lg n)\)。
\(\begin{aligned} T_{b2}(N,n)&=2T_{b2}(N,n/2)+\Theta(N)\\ &=4T_{a2}(N,n/4)+2\Theta(N)+\Theta(N)\\ &=8T_{a2}(N,n/8)+4\Theta(N)+2\Theta(N)+\Theta(N)\\ &\dots\\ &=\sum_{i=0}^{\lfloor\lg n\rfloor-1} 2^i\cdot\Theta(N)\\ &=\Theta(Nn) \end{aligned}\)
\(T_{b3}:T_{b3}(N,n)=T_{b1}(N,n)=\Theta(n\lg n)\)。
\(T_{c1}:a=8,b=2,f(n)=\Theta(1),\log_ba=3\)。因此根据第一个条件，\(T_{c1}(N,n)=\Theta(n^3)\)。
\(\begin{aligned} T_{c2}(N,n)&=8T_{c2}(N,n/2)+\Theta(N^2)\\ &=64T_{a2}(N,n/4)+8\Theta(N)+\Theta(N)\\ &=512T_{a2}(N,n/8)+64\Theta(N)+8\Theta(N)+\Theta(N)\\ &\dots\\ &=\sum_{i=0}^{\lfloor\lg n\rfloor-1} 8^i\cdot\Theta(N)\\ &=\Theta(Nn^3) \end{aligned}\)
\(T_{c3}:a=8,b=2,f(n)=\Theta(n^2),\log_ba=3\)。因此根据第一个条件，\(T_{c1}(N,n)=\Theta(n^3)\)。
4-3
a
代入\(n=2^m\)。那么可以写成\(T(2^m)=2T(2^{m/2})+\Theta(m)\)。
再代入\(S(m)=T(2^m)\)，那么有\(S(m)=2S(m/2)+\Theta(m)\)。
b
\(a=2,b=2,f(n)=\Theta(n),\log_ba=1\)。因此根据第二个条件，得到\(k=0\)，最终\(S(m)=\Theta(m\lg m)\)。
c
由于\(S(2^m)=\Theta(m\lg m)\)，回代\(n=2^m\)，即\(m=\lg n\)，得到\(T(n)=\Theta(\lg n\cdot \lg \lg n)\)。
d
可以发现，整个递归树一共只有\(\Theta(\lg \lg n)\)层。
如图所示，最终有\(T(n)=\lg\lg n\cdot \Theta(\lg n)=\Theta(\lg n\cdot\lg \lg n)\)。
e
代入\(n=2^m\)。那么可以写成\(T(2^m)=2T(2^{m/2})+\Theta(1)\)。
再代入\(S(m)=T(2^m)\)，那么有\(S(m)=2S(m/2)+\Theta(1)\)。
\(a=2,b=2,f(m)=\Theta(1),\log_ba=1\)。因此根据第一个条件，\(S(m)=\Theta(m)\)。
回代\(n=2^m\)，即\(m=\lg n\)，得到\(T(n)=\Theta(\lg n)\)。
f
代入\(n=3^m\)。那么可以写成\(T(3^m)=3T(3^{m/3})+\Theta(3^m)\)。
再代入\(S(m)=T(3^m)\)，那么有\(S(m)=3S(m/3)+\Theta(3^m)\)。
\(\begin{aligned} S(m)&=3S(m/3)+\Theta(3^m)\\ &=9S(m/9)+3\cdot \Theta(3^{m-1})+\Theta(3^m)\\ &=27S(m/27)+9\cdot \Theta(3^{m-2})+3\cdot \Theta(3^{m-1})+\Theta(3^m)\\ &\dots\\ &=\sum_{i=0}^{\lfloor\log_3 m\rfloor-1} \Theta(3^m)\\ &=\Theta(\lg m\cdot3^m) \end{aligned}\)
回代\(n=3^m\)，即\(m=\log_3 n\)，得到\(T(n)=\Theta(n\cdot \lg \lg n)\)。
4-4
a
考虑使用主定理，那么有\(a=5,b=3,f(n)=n\lg n,\log _b a=\log_3 5>1\)
因此根据第一个条件，\(T(n)=\Theta(n^{\log_3 5})\)
b
由于\(a=3,b=3,f(n)=n/\lg n=\Theta(n^{\log_b a}/\lg n)\)。
那么使用题目4.6-3的结论，得到\(T(n)=n\lg\lg n\)。
c
考虑使用主定理，那么有\(a=8,b=2,f(n)=n^{7/2},\log _b a=3\)
因此根据第三个条件，可以构造出\(c=\dfrac{\sqrt{2}}{2}\)，最终\(T(n)=\Theta(n^{7/2})\)。
d
根据4-3节的结论，常数附加项不会对递推式的渐进结果产生影响。
因此令\(T'(n)=2T'(n/2)+n/2\)，那么\(T(n)=\Theta(T'(n))\)。
考虑使用主定理求解\(T'(n)\)，那么有\(a=2,b=2,f(n)=n/2,\log _b a=\log_2 2=1\)
因此根据第二个条件，得到\(k=0\)，最终\(T'(n)=\Theta(n\lg n)\)。
也就是说，\(T(n)=\Theta(n\lg n)\)。
e
由于\(a=2,b=2,f(n)=n/\lg n=\Theta(n^{\log_b a}/\lg n)\)。
那么使用题目4.6-3的结论，得到\(T(n)=n\lg\lg n\)。
f
考虑使用Akra-Bazzi方法。
由于\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i}=\dfrac{7}{8}}\)，因此\(p<1\)。如果精确解方程\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i^p}=1}\)，那么可以得到\(p\approx 0.879146\)。并且由于\(f(n)=n\)。那么有
\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n^p\left(1+\int_{1}^n x^{-p}dx\right)\right)\\ &=\Theta\left(n^p\left(1+\left(\left.\dfrac{x^{1-p}}{1-p}\right|_{1}^n\right)\right)\right)\\ &=\Theta\left(n^p\left(1+\left(\dfrac{n^{1-p}-1}{1-p}\right)\right)\right)\\ &=\Theta\left(n^p+\dfrac{n-n^p}{1-p}\right)\\ &=\Theta(n) \end{aligned}\)
g
\(\begin{aligned} T(n)&=T(n-1)+\dfrac{1}{n}\\ &=T(n-2)+\dfrac{1}{n-1}+\dfrac{1}{n}\\ &=\sum_{i=1}^n\dfrac{1}{i}\\ &=\ln n+O(1)\\ &=\Theta(\lg n) \end{aligned}\)
h
\(\begin{aligned} T(n)&=T(n-1)+\lg n\\ &=T(n-2)+\lg (n-1)+\lg n\\ &=\sum_{i=1}^n\lg i\\ &=\lg n!\\ &=\Theta(n\lg n) \end{aligned}\)
i
本题目答案参考了此页面的内容，并且更加严谨了一些。
可以发现，\(T(n)\)可以写成如下分段等式：
\[ T(n)= \left \{\begin{aligned} &T(0)+\sum_{k=1}^{n/2}\dfrac{1}{\lg(2k)} & &\text{if }n \equiv 0 \pmod 2\\ &T(1)+\sum_{k=1}^{(n-1)/2}\dfrac{1}{\lg(2k+1)}& &\text{if }n \equiv 1 \pmod 2 \end{aligned}\right. \]
接下来证明\(T(n)=\Omega\left(\dfrac{n}{\lg n}\right).\)
当\(n\)为偶数时，有\(\displaystyle{T(n)=T(0)+\sum_{k=1}^{n/2}\dfrac{1}{\lg(2k)}\ge T(0)+\sum_{k=1}^{n/2}\dfrac{1}{\lg n}=T(0)+\dfrac{n}{2\lg n}\ge \dfrac{n}{2\lg n}}.\)不难发现在这种情况下有\(T(n)=\Omega\left(\dfrac{n}{\lg n}\right).\)
当\(n\)为奇数时，有\(\displaystyle{T(n)=T(1)+\sum_{k=1}^{(n-1)/2}\dfrac{1}{\lg(2k+1)}\ge T(1)+\sum_{k=1}^{(n-1)/2}\dfrac{1}{\lg n}=T(1)+\dfrac{n-1}{2\lg n}\ge \dfrac{n}{2\lg n}}.\)不难发现在这种情况下有\(T(n)=\Omega\left(\dfrac{n}{\lg n}\right).\)
因此综上所述，\(T(n)=\Omega\left(\dfrac{n}{\lg n}\right).\)
接下来证明\(T(n)=O\left(\dfrac{n}{\lg n}\right).\)以下变换基于\(n\ge e^2\)的假设进行。
当\(n\)为偶数时，有
\(\begin{aligned} T(n)&=\sum_{k=1}^{n/2}\dfrac{1}{\lg(2k)}\\ &=\dfrac{1}{\lg 2}+\sum_{k=2}^{n/2}\dfrac{1}{\lg(2k)}\\ &\le 1+\int_1^{n/2}\dfrac{dx}{\lg(2x)}\\ &= 1+\dfrac{1}{2}\int_2^{n}\dfrac{dx}{\lg x}\\ &={\color{red}1+\dfrac{1}{2}\int_2^{e^2}\dfrac{dx}{\lg x}}+\dfrac{1}{2}\int_{e^2}^n\dfrac{dx}{\lg x} \end{aligned}\)
当\(n\)为奇数时，有
\(\begin{aligned} T(n)&=\sum_{k=1}^{(n-1)/2}\dfrac{1}{\lg(2k+1)}\\ &=\dfrac{1}{\lg 3}+\sum_{k=2}^{(n-1)/2}\dfrac{1}{\lg(2k+1)}\\ &\le \dfrac{1}{\lg 3}+\int_1^{(n-1)/2}\dfrac{dx}{\lg(2x+1)}\\ &= \dfrac{1}{\lg 3}+\dfrac{1}{2}\int_3^{n}\dfrac{dx}{\lg x}\\ &={\color{red}\dfrac{1}{\lg 3}+\dfrac{1}{2}\int_3^{e^2}\dfrac{dx}{\lg x}}+\dfrac{1}{2}\int_{e^2}^n\dfrac{dx}{\lg x} \end{aligned}\)
因此，令\(\displaystyle{c_0=\max\left\{1+\dfrac{1}{2}\int_2^{e^2}\dfrac{dx}{\lg x},\dfrac{1}{\lg 3}+\dfrac{1}{2}\int_3^{e^2}\dfrac{dx}{\lg x}\right\}}\)。那么可以写成
\[T(n)\le c+\dfrac{1}{2}\int_{e^2}^n\dfrac{dx}{\lg x}=c+\dfrac{\ln 2}{2}\int_{e^2}^n\dfrac{dx}{\ln x}\]
当\(n\ge e^2\)时，不难得到不等式\(\ln n\le 2(\ln n -1)\)。故此有
\(\begin{aligned} T(n)&\le c+\dfrac{\ln 2}{2}\int_{e^2}^n\dfrac{dx}{\ln x}\\ &\le c+\ln 2\cdot\int_{e^2}^n\dfrac{(\ln x-1)dx}{\ln^2 x}\\ &= c+\ln 2\cdot\left(\left.\dfrac{x}{\ln x}\right|_{e^2}^n\right)\\ &= c+\dfrac{n\cdot\ln 2}{\ln n}-\dfrac{e^2\cdot \ln 2 }{2} \end{aligned}\)
因此综上所述，\(T(n)=O\left(\dfrac{n}{\lg n}\right).\)
最终有\(T(n)=\Theta\left(\dfrac{n}{\lg n}\right).\)
j
令\(U(n)=\dfrac{T(n)}{n}\)。将\(U(n)\)代入到原式，那么得到
\[U(n)=U(\sqrt{n})+1\]
令\(V(m)=U(2^m)\)。将\(V(m)\)带入到上式，那么得到
\[V(m)=V(m/2)+1\]
根据主定理的第二个条件，可以得到\(V(m)=\Theta(\lg m)\)。
回代到\(U\)中，得到\(U(n)=\Theta(\lg \lg n)\)。
因此有\(T(n)=\Theta(n\lg \lg n)\)。
4-5
a
将一次项和常数项目全部分离出来，那么等式右边三项可以写成：
\(\begin{aligned} &z=z\\ &z\mathcal{F}(z)=\sum_{i=0}^{\infty} F_iz^{i+1}=\sum_{i=1}^{\infty} F_{i-1} z^i=F_0 z+\sum_{i=2}^{\infty} F_{i-1}z^i\\ &z^2\mathcal{F}(z)=\sum_{i=0}^{\infty} F_iz^{i+2}=\sum_{i=2}^{\infty} F_{i-2} z^i\\ \end{aligned}\)
三项相加，得到\(\displaystyle{z+\sum_{i=2}^{\infty} (F_{i-1}+F_{i-2})z^i=z+\sum_{i=2}^{\infty}F_iz^i}\)。
代入\(F_0=0,F_1=1\)，最终这个式子可以写成\(\displaystyle{\sum_{i=0}^{\infty}F_iz^i}\)，也就是\(\mathcal{F}(z)\)。
b
将a的结论整理得到\(\mathcal{F}(z)-z\mathcal{F}(z)-z^2\mathcal{F}(z)=z\)，提取\(\mathcal{F}(z)\)公因式，得到\(\mathcal{F}(z)(1-z-z^2)=z\)，最终得到：
\(\mathcal{F}(z)=\dfrac{z}{1-z-z^2}\)
由于\(\phi=\dfrac{1+\sqrt{5}}{2},\hat{\phi}=\dfrac{1-\sqrt{5}}{2}\)，那么得到\(\phi\cdot \hat{\phi}=-1,\phi+\hat{\phi}=1,\phi-\hat{\phi}=\sqrt{5}\)。
由于\((1-\phi z)(1-\hat{\phi z})=\phi\cdot \hat{\phi} \cdot z^2-(\phi + \hat{\phi}) z+1=1-z-z^2\)，因此\(\mathcal{F}(z)\)还可以写成：\(\mathcal{F}(z)=\dfrac{z}{(1-\phi z)(1-\hat{\phi}z)}\)
由于有如下变换：
\(\begin{aligned} \dfrac{1}{\sqrt{5}}\left(\dfrac{1}{1-\phi z}-\dfrac{1}{1-\hat{\phi}z}\right)&=\dfrac{1}{\sqrt{5}}\left(\dfrac{(1-\hat{\phi} z)-(1-\phi z)}{(1-\phi z)(1-\hat{\phi}z)}\right)\\ &=\dfrac{1}{\sqrt{5}}\left(\dfrac{\phi-\hat{\phi}}{(1-\phi z)(1-\hat{\phi}z)}\right)\\ &=\dfrac{1}{(1-\phi z)(1-\hat{\phi}z)} \end{aligned}\)
因此\(\mathcal{F}(z)\)还可以写成：\(\mathcal{F}(z)=\dfrac{1}{\sqrt{5}}\left(\dfrac{1}{1-\phi z}-\dfrac{1}{1-\hat{\phi}z}\right)\).
c
\(\begin{aligned} \mathcal{F}(z)&=\dfrac{1}{\sqrt{5}}\left(\dfrac{1}{1-\phi z}-\dfrac{1}{1-\hat{\phi}z}\right)\\ &=\dfrac{1}{\sqrt{5}}\left(\sum_{i=0}^{\infty} \phi^iz^i-\sum_{i=0}^{\infty} \hat{\phi}^iz^i\right)\\ &=\dfrac{1}{\sqrt{5}}\sum_{i=0}^{\infty} (\phi^i- \hat{\phi}^i)z^i\\ \end{aligned}\)
d
由题目c得到的等式，代入题目求和项中的\(F_i\)，有\(F_i=\dfrac{\phi^i- \hat{\phi}^i}{\sqrt{5}}=\dfrac{\phi^i}{\sqrt{5}}-\dfrac{\hat{\phi}^i}{\sqrt{5}}\)。
可以发现，对于\(\forall i\ge 0,\left|\dfrac{\hat{\phi}^i}{\sqrt{5}}\right|<0.5\)均成立。因此，\(F_i'=\dfrac{\hat{\phi}^i}{\sqrt{5}}\)最接近的整数即为\(F_i\)。
e
考虑式子\(F_{i+2}-\phi^i\)的值。那么有
\(F_{i+2}-\phi ^i=\dfrac{1}{\sqrt{5}}\left(\phi^{i+2}-\hat{\phi}^{i+2}\right)-\phi^i=\dfrac{3\sqrt{5}-5}{10} \phi^i-\dfrac{3\sqrt{5}-5}{10}\hat{\phi}^{i}=\dfrac{3\sqrt{5}-5}{10}(\phi^i-\hat{\phi}^i)\)
由于\(\phi>\hat{\phi}\)，因此\(F_{i+2}-\phi^i\ge 0\)，即有\(F_{i+2}\ge \phi^i\)。
4-6
a
假设好的芯片一共有\(k\)个，其中满足\(k\le n-k\)。
那么从这\(n-k\)个坏芯片中选择出\(k\)个坏芯片。这\(k\)个坏芯片的策略是：如果另一个芯片是好芯片，那么显示为坏结果如果另一个芯片是坏芯片，那么显示为好结果。
按照这种策略，只要从这\(2k\)个芯片中取出任意\(2\)个芯片检测，那么教授旧无法区分哪\(k\)个芯片是好的，哪\(k\)个芯片是坏的，因为两个芯片互相检测结果总是一致的，
b
现在题目的假设是：好芯片严格多于坏芯片。
整个策略如下：首先，如果当前芯片个数\(n\)是奇数，那么均匀随机选择一个芯片留下，对剩下的\(n-1\)个芯片进行递归操作，等操作完成再回头考虑这个被留下的芯片；否则什么都不用做。在一轮中，每次随机取出\(2\)个芯片进行测试。如果\(2\)个芯片的测试结果是“\(2\)个都是好芯片”，那么丢弃其中\(1\)个芯片，另\(1\)个芯片留到下一轮测试；否则\(2\)个芯片都丢弃。这个过程由算法GET-GOOD描述。
1 | // 子程序`TEST(c1, c2)`表示对芯片c1, c2进行测试的结果。用True表示全好的报告，用False表示存在1个芯片是坏的报告。 |
因此在一轮测试中，需要进行\(\left\lfloor\dfrac{n}{2}\right\rfloor\)次测试。在一轮测试完成后，最多剩下\(\left\lceil\dfrac{n}{2}\right\rceil\)个芯片。
接下来说明：经过一轮的测试后，剩下的芯片仍然满足：好芯片仍然严格多于坏芯片。
可以知道，如果算法GET-GOOD传入的芯片中，好坏的个数相同，那么最终这个算法的递归终点将是第2行的NIL。因为在第7行的for循环完成后，得到的C数组中，好芯片和坏芯片的个数仍然相同。最终随着递归的进行，每一对好坏芯片都将被抵消，最终找不到任何一个好芯片。
如果算法GET-GOOD传入的芯片中，好芯片要比坏芯片多，那么在这一轮测试中，假设芯片的个数为\(n\)，那么考虑如下\(2\)个情况：
如果\(n\)是偶数，在这\(\dfrac{n}{2}\)次测试中，有\(a\)次是拿出了\(2\)个好芯片进行测试，有\(b\)次是拿出了\(1\)个好芯片，\(1\)个坏芯片进行测试，有\(c\)次是拿出了\(2\)个坏芯片进行测试，需要注意的是，在测试的过程中，\(a,b,c\)的值是无法被统计。那么可以知道好芯片的个数为\(2a+b\)，坏芯片的个数为\(2c+b\)。按照假设，有\(2a+b>2c+b\)，即得出\(a>c\)。在\(b\)次不同好坏芯片的测试中，所有芯片都丢弃；\(a\)次全好芯片测试中，将会恰好保留\(a\)个好芯片；在\(c\)次全坏芯片测试中，将会至多保留\(c\)个坏芯片（因为两个坏芯片同样会有可能报告对方是坏的）。由于\(a>c\)，因此这一轮测试完成后，保留的好芯片必然严格多于坏芯片。最终递归终止时，所有坏芯片将会被丢弃，通过第4行的代码找到一个好芯片。
如果\(n\)是奇数，那么有如下\(2\)种情况进行讨论，注意需要随机留出一个芯片，假设为chips[0]。
1
如果算法GET-GOOD传入的芯片中，好芯片要比坏芯片多出\(3\)个或以上，那么无论留下来的是好芯片还是坏芯片，按照偶数时的情况，第16行代码中，变量now必定是一个好芯片，直接返回。
2
如果算法GET-GOOD传入的芯片中，好芯片要比坏芯片多出恰好\(1\)个，那么有如下\(2\)情况讨论。
如果留下来的是好芯片，那么剩下的\(n-1\)个芯片中，好坏的个数相同。上面13行的for循环完成后，数组C的好坏芯片个数相同。按照上面的结论，第16行代码对数组C进行递归调用后，得到的必定是NIL。那么返回留下的好芯片chips[0]即可。
如果留下来的是坏芯片，那么剩下的\(n-1\)个芯片中，好芯片多于坏芯片。按照偶数时的结论，第16行代码中，变量now必定是一个好芯片，直接返回。
故在好芯片严格多于坏芯片的情况下，算法GET-GOOD总能找到一个好芯片。
c
根据题目4-6-b的结论，假设\(n\)个芯片的比较次数为\(T(n)\)，那么可以给出下列不等式：
\(T(n)\le T\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right)+\left\lfloor\dfrac{n}{2}\right\rfloor\)
根据主定理的第二个条件，不难得到\(T(n)=O(n)\)。
d
由于找出一个好的芯片需要\(O(n)\)次比较，那么使用这个好的芯片对其它芯片进行测试就能够找到所有好芯片，总共需要\(n-1\)次比较。
因此，最终找到所有好芯片的次数为\(O(n)+n-1=\Theta(n)\)次。
4-7
a
充分性：
令\(k=i+1,k=j+1\)，那么得到等式\(A[i,j]+A[i+1,j+1]\le A[i,j+1]+A[i+1,j]\)。充分性成立。
必要性：
由\(A[i,j]+A[i+1,j+1]\le A[i,j+1]+A[i+1,j]\)通过移项，得到：
\(A[i,j]-A[i,j+1]\le A[i+1,j]-A[i+1,j+1]\)。
令函数\(f_j(x)=A[x,j]-A[x,j+1]\)，那么对于\(1\le x<m\)，由上面的等式，发现\(f_j(i)\)是一个递增函数。因此，\(\forall 1\le i< k\le m\)，都有\(f_j(i)\le f_j(k)\)成立。即有\(A[i,j]+A[k,j+1]\le A[i,j+1]+A[k,j]\)都成立。
同理，可以得出\(\forall 1\le j< l\le n\)，都有\(A[i,j]+A[i+1,l]\le A[i,l]+A[i+1,j]\)。
最终根据传递性，总有\(A[i,j]+A[k,l]\le A[i,l]+A[l,j]\)成立，因此必要性成立。
b
\(\begin{aligned} &&37 &&23 &&\mathbf{29} &&32 \\ &&21 &&6 &&7 &&10 \\ &&53 &&34 &&30 &&31 \\ &&32 &&13 &&9 &&6 \\ &&43 &&21 &&15 &&6 \\ \end{aligned}\)
c
本题使用反正法进行证明。
假设存在\(a,b\)满足\(1\le a< b\le m\)，有\(f(a)>f(b)\)。
根据\(f\)函数的定义：\(f(i)\)是第\(i\)行中最左的最小元素的列下标，可以得到：\(A[a,f(b)]>A[a,f(a)]\)，注意此式子不能取等号；还可以得到\(A[b,f(b)]\le A[b,f(a)]\).
根据这两条不等式可以得到\(A[b,f(a)]+A[a,f(b)]>A[a,f(a)]+A[b,f(b)]\)，与Monge矩阵的定义矛盾。
因此\(\forall 1\le a< b\le m\)，都有\(f(a)\le f(b)\)。
d
由于目前已经知道\(f(2),f(4),f(6),\dots,f(2k)\)的值，并且由于已知\(f(0)\le f(1)\le f(2)\le f(3)\le \dots \le f(m)\)。为了计算\(f(1),f(3),f(5),\dots,f(2k+1)\)的值，假设\(f(0)=1\)，有：
\(\begin{aligned} S(n,m)&=\sum_{i=1}^{m/2} (f(2i)-f(2i-2)+1)\\ &=f(m)-f(0)+m/2\\ &=O(n+m) \end{aligned}\)
e
为了解决整个求解问题，可以写出\(S(m)=S(m/2)+T(n,m)\)。
由于\(T(n,m)=O(n+m)\)，那么可以假设\(T(n,m)\le an+bm\)
\(\begin{aligned} S(m)&\le S(m/2)+an+bm\\ &\le S(m/4)+an+bm+an+bm/2\\ &\le S(m/8)+an+bm+an+bm/2+an+bm/4\\ &\le \dots\\ &=\sum_{i=0}^{\lfloor\lg m\rfloor} an+\dfrac{bm}{2^i}\\ &= bm+an\lg m \end{aligned}\)
因此\(S(m)=O(m+n\lg m)\)。