算法导论 4 Problems 答案

4-1

a

$a=2,b=2,f(n)=n^3,{\log }_{b}a=1$

因此根据第三个条件，可以构造出 $c={\displaystyle \frac{1}{8}}$，最终 $T(n)=\mathrm{\Theta }(n^3)$

b

$a=1,b={\displaystyle \frac{11}{8}},f(n)=n,{\log }_{b}a=0$

因此根据第三个条件，可以构造出 $c={\displaystyle \frac{8}{11}}$，最终 $T(n)=\mathrm{\Theta }(n)$

c

$a=16,b=4,f(n)=n^2,{\log }_{b}a=2$

因此根据第二个条件，得到 $k=0$，最终 $T(n)=\mathrm{\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)=\mathrm{\Theta }(n^2\cdot {\lg }^{2}n)$

e

$a=8,b=3,f(n)=n^2,{\log }_{b}a={\log }_{3}8<2$

因此根据第三个条件，可以构造出 $c={\displaystyle \frac{8}{9}}$，最终 $T(n)=\mathrm{\Theta }(n^2)$

f

$a=7,b=2,f(n)=n^2\lg n,{\log }_{b}a={\log }_{2}7>2$

因此根据第一个条件，$T(n)=\mathrm{\Theta }(n^{\lg 7})$

g

$a=2,b=4,f(n)=\sqrt{n},{\log }_{b}a={\log }_{4}2={\displaystyle \frac{1}{2}}$

因此根据第二个条件，得到 $k=0$，最终 $T(n)=\mathrm{\Theta }(\sqrt{n}\cdot \lg n)$

h

令 $m=nmod2$，可以知道，$m\in \{0,1\}$。

那么有：

$\begin{array}{rl}T(n)& =\sum _{k=0}^{n/2}(2k+m{)}^2\\ & =\sum _{k=0}^{n/2}(4k^2+4km+m^2)\\ & ={\displaystyle \frac{m^{2}n}{2}}+\sum _{k=0}^{n/2}(4k^2+4km)\\ & ={\displaystyle \frac{m^{2}n}{2}}+4\sum _{k=0}^{n/2}{k}^2+4m\sum _{k=0}^{n/2}k\\ & ={\displaystyle \frac{m^{2}n}{2}}+4\cdot {\displaystyle \frac{n/2\cdot (n/2+1)(n+1)}{6}}+4m\cdot {\displaystyle \frac{n/2\cdot (n/2+1)}{2}}\\ & =\mathrm{\Theta }(n^3)\end{array}$

4-2

$\begin{array}{rl}& T_{a1}(N,n)=T_{a1}(N,n/2)+\mathrm{\Theta }(1)\\ & T_{a2}(N,n)=T_{a2}(N,n/2)+\mathrm{\Theta }(N)\\ & T_{a3}(N,n)=T_{a3}(N,n/2)+\mathrm{\Theta }(n)\\ & T_{b1}(N,n)=2T_{b1}(N,n/2)+\mathrm{\Theta }(1)+\mathrm{\Theta }(n)\\ & T_{b2}(N,n)=2T_{b2}(N,n/2)+\mathrm{\Theta }(N)\\ & T_{b3}(N,n)=2T_{b3}(N,n/2)+\mathrm{\Theta }(n)\\ & T_{c1}(N,n)=8T_{c1}(N,n/2)+\mathrm{\Theta }(1)\\ & T_{c2}(N,n)=8T_{c2}(N,n/2)+\mathrm{\Theta }(N^2)\\ & T_{c3}(N,n)=8T_{c3}(N,n/2)+\mathrm{\Theta }(n^2)\end{array}$

$T_{a1}:a=1,b=2,f(n)=\mathrm{\Theta }(1),{\log }_{b}a=0$。因此根据第二个条件，得到 $k=0$，最终 $T_{a1}(N,n)=\mathrm{\Theta }(\lg n)$。

$\begin{array}{rl}{T}_{a2}(N,n)& =T_{a2}(N,n/2)+\mathrm{\Theta }(N)\\ & =T_{a2}(N,n/4)+\mathrm{\Theta }(N)+\mathrm{\Theta }(N)\\ & =T_{a2}(N,n/8)+\mathrm{\Theta }(N)+\mathrm{\Theta }(N)+\mathrm{\Theta }(N)\\ & \dots \\ & =\sum _{i=0}^{\lfloor \lg n\rfloor -1}\mathrm{\Theta }(N)\\ & =\mathrm{\Theta }(N\cdot \lg n)\end{array}$

$T_{a3}:a=1,b=2,f(n)=\mathrm{\Theta }(n),{\log }_{b}a=0$。因此根据第三个条件，可以构造出 $c={\displaystyle \frac{1}{2}}$，最终 $T_{a3}(N,n)=\mathrm{\Theta }(n)$。

$T_{b1}:a=2,b=2,f(n)=\mathrm{\Theta }(n),{\log }_{b}a=1$。因此根据第二个条件，得到 $k=0$，最终 $T_{b1}(N,n)=\mathrm{\Theta }(n\lg n)$。

$\begin{array}{rl}{T}_{b2}(N,n)& =2T_{b2}(N,n/2)+\mathrm{\Theta }(N)\\ & =4T_{a2}(N,n/4)+2\mathrm{\Theta }(N)+\mathrm{\Theta }(N)\\ & =8T_{a2}(N,n/8)+4\mathrm{\Theta }(N)+2\mathrm{\Theta }(N)+\mathrm{\Theta }(N)\\ & \dots \\ & =\sum _{i=0}^{\lfloor \lg n\rfloor -1}{2}^i\cdot \mathrm{\Theta }(N)\\ & =\mathrm{\Theta }(Nn)\end{array}$

$T_{b3}:T_{b3}(N,n)=T_{b1}(N,n)=\mathrm{\Theta }(n\lg n)$。

$T_{c1}:a=8,b=2,f(n)=\mathrm{\Theta }(1),{\log }_{b}a=3$。因此根据第一个条件，$T_{c1}(N,n)=\mathrm{\Theta }(n^3)$。

$\begin{array}{rl}{T}_{c2}(N,n)& =8T_{c2}(N,n/2)+\mathrm{\Theta }(N^2)\\ & =64T_{a2}(N,n/4)+8\mathrm{\Theta }(N)+\mathrm{\Theta }(N)\\ & =512T_{a2}(N,n/8)+64\mathrm{\Theta }(N)+8\mathrm{\Theta }(N)+\mathrm{\Theta }(N)\\ & \dots \\ & =\sum _{i=0}^{\lfloor \lg n\rfloor -1}{8}^i\cdot \mathrm{\Theta }(N)\\ & =\mathrm{\Theta }(N{n}^3)\end{array}$

$T_{c3}:a=8,b=2,f(n)=\mathrm{\Theta }(n^2),{\log }_{b}a=3$。因此根据第一个条件，$T_{c1}(N,n)=\mathrm{\Theta }(n^3)$。

4-3

a

代入 $n=2^m$。那么可以写成 $T(2^m)=2T(2^{m/2})+\mathrm{\Theta }(m)$。

再代入 $S(m)=T(2^m)$，那么有 $S(m)=2S(m/2)+\mathrm{\Theta }(m)$。

b

$a=2,b=2,f(n)=\mathrm{\Theta }(n),{\log }_{b}a=1$。因此根据第二个条件，得到 $k=0$，最终 $S(m)=\mathrm{\Theta }(m\lg m)$。

c

由于 $S(2^m)=\mathrm{\Theta }(m\lg m)$，回代 $n=2^m$，即 $m=\lg n$，得到 $T(n)=\mathrm{\Theta }(\lg n\cdot \lg \lg n)$。

d

可以发现，整个递归树一共只有 $\mathrm{\Theta }(\lg \lg n)$ 层。

如图所示，最终有 $T(n)=\lg \lg n\cdot \mathrm{\Theta }(\lg n)=\mathrm{\Theta }(\lg n\cdot \lg \lg n)$。

e

代入 $n=2^m$。那么可以写成 $T(2^m)=2T(2^{m/2})+\mathrm{\Theta }(1)$。

再代入 $S(m)=T(2^m)$，那么有 $S(m)=2S(m/2)+\mathrm{\Theta }(1)$。

$a=2,b=2,f(m)=\mathrm{\Theta }(1),{\log }_{b}a=1$。因此根据第一个条件，$S(m)=\mathrm{\Theta }(m)$。

回代 $n=2^m$，即 $m=\lg n$，得到 $T(n)=\mathrm{\Theta }(\lg n)$。

f

代入 $n=3^m$。那么可以写成 $T(3^m)=3T(3^{m/3})+\mathrm{\Theta }(3^m)$。

再代入 $S(m)=T(3^m)$，那么有 $S(m)=3S(m/3)+\mathrm{\Theta }(3^m)$。

$\begin{array}{rl}S(m)& =3S(m/3)+\mathrm{\Theta }(3^m)\\ & =9S(m/9)+3\cdot \mathrm{\Theta }(3^{m-1})+\mathrm{\Theta }(3^m)\\ & =27S(m/27)+9\cdot \mathrm{\Theta }(3^{m-2})+3\cdot \mathrm{\Theta }(3^{m-1})+\mathrm{\Theta }(3^m)\\ & \dots \\ & =\sum _{i=0}^{\lfloor {\log }_{3}m\rfloor -1}\mathrm{\Theta }(3^m)\\ & =\mathrm{\Theta }(\lg m\cdot 3^m)\end{array}$

回代 $n=3^m$，即 $m={\log }_{3}n$，得到 $T(n)=\mathrm{\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)=\mathrm{\Theta }(n^{{\log }_{3}5})$

b

由于 $a=3,b=3,f(n)=n/\lg n=\mathrm{\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={\displaystyle \frac{\sqrt{2}}{2}}$，最终 $T(n)=\mathrm{\Theta }(n^{7/2})$。

d

根据 4-3 节的结论，常数附加项不会对递推式的渐进结果产生影响。

因此令 $T^{\prime }(n)=2T^{\prime }(n/2)+n/2$，那么 $T(n)=\mathrm{\Theta }(T^{\prime }(n))$。

考虑使用主定理求解 $T^{\prime }(n)$，那么有 $a=2,b=2,f(n)=n/2,{\log }_{b}a={\log }_{2}2=1$

因此根据第二个条件，得到 $k=0$，最终 $T^{\prime }(n)=\mathrm{\Theta }(n\lg n)$。

也就是说，$T(n)=\mathrm{\Theta }(n\lg n)$。

e

由于 $a=2,b=2,f(n)=n/\lg n=\mathrm{\Theta }(n^{{\log }_{b}a}/\lg n)$。

那么使用题目 4.6-3 的结论，得到 $T(n)=n\lg \lg n$。

f

考虑使用 Akra-Bazzi 方法。

由于 ${\displaystyle \sum _{i=1}^k{\displaystyle \frac{a_i}{b_i}}={\displaystyle \frac{7}{8}}}$，因此 $p<1$。如果精确解方程 ${\displaystyle \sum _{i=1}^k{\displaystyle \frac{a_i}{b_i^p}}=1}$，那么可以得到 $p\approx 0.879146$。并且由于 $f(n)=n$。那么有

$\begin{array}{rl}T(n)& =\mathrm{\Theta }\left(n^p(1+{\int }_1^n{\displaystyle \frac{f(x)}{x^{p+1}}}dx)\right)\\ & =\mathrm{\Theta }\left(n^p(1+{\int }_1^n{x}^{-p}dx)\right)\\ & =\mathrm{\Theta }\left(n^p(1+\left({{\displaystyle \frac{x^{1-p}}{1-p}}|}_1^n\right))\right)\\ & =\mathrm{\Theta }\left(n^p(1+\left({\displaystyle \frac{n^{1-p}-1}{1-p}}\right))\right)\\ & =\mathrm{\Theta }(n^p+{\displaystyle \frac{n-n^p}{1-p}})\\ & =\mathrm{\Theta }(n)\end{array}$

g

$\begin{array}{rl}T(n)& =T(n-1)+{\displaystyle \frac{1}{n}}\\ & =T(n-2)+{\displaystyle \frac{1}{n-1}}+{\displaystyle \frac{1}{n}}\\ & =\sum _{i=1}^n{\displaystyle \frac{1}{i}}\\ & =\ln n+O(1)\\ & =\mathrm{\Theta }(\lg n)\end{array}$

h

$\begin{array}{rl}T(n)& =T(n-1)+\lg n\\ & =T(n-2)+\lg (n-1)+\lg n\\ & =\sum _{i=1}^n\lg i\\ & =\lg n!\\ & =\mathrm{\Theta }(n\lg n)\end{array}$

i

本题目答案参考了此页面的内容，并且更加严谨了一些。

可以发现，$T(n)$ 可以写成如下分段等式：

$$T(n)=\{\begin{array}{rlrl}& T(0)+\sum _{k=1}^{n/2}{\displaystyle \frac{1}{\lg (2k)}}& & \text{if }n\equiv 0(\mathrm{mod}2)\\ & T(1)+\sum _{k=1}^{(n-1)/2}{\displaystyle \frac{1}{\lg (2k+1)}}& & \text{if }n\equiv 1(\mathrm{mod}2)\end{array}$$

接下来证明 $T(n)=\mathrm{\Omega }\left({\displaystyle \frac{n}{\lg n}}\right).$

当 $n$ 为偶数时，有 ${\displaystyle T(n)=T(0)+\sum _{k=1}^{n/2}{\displaystyle \frac{1}{\lg (2k)}}\ge T(0)+\sum _{k=1}^{n/2}{\displaystyle \frac{1}{\lg n}}=T(0)+{\displaystyle \frac{n}{2\lg n}}\ge {\displaystyle \frac{n}{2\lg n}}.}$ 不难发现在这种情况下有 $T(n)=\mathrm{\Omega }\left({\displaystyle \frac{n}{\lg n}}\right).$

当 $n$ 为奇数时，有 ${\displaystyle T(n)=T(1)+\sum _{k=1}^{(n-1)/2}{\displaystyle \frac{1}{\lg (2k+1)}}\ge T(1)+\sum _{k=1}^{(n-1)/2}{\displaystyle \frac{1}{\lg n}}=T(1)+{\displaystyle \frac{n-1}{2\lg n}}\ge {\displaystyle \frac{n}{2\lg n}}.}$ 不难发现在这种情况下有 $T(n)=\mathrm{\Omega }\left({\displaystyle \frac{n}{\lg n}}\right).$

因此综上所述，$T(n)=\mathrm{\Omega }\left({\displaystyle \frac{n}{\lg n}}\right).$

接下来证明 $T(n)=O\left({\displaystyle \frac{n}{\lg n}}\right).$ 以下变换基于 $n\ge e^2$ 的假设进行。

当 $n$ 为偶数时，有

$\begin{array}{rl}T(n)& =\sum _{k=1}^{n/2}{\displaystyle \frac{1}{\lg (2k)}}\\ & ={\displaystyle \frac{1}{\lg 2}}+\sum _{k=2}^{n/2}{\displaystyle \frac{1}{\lg (2k)}}\\ & \le 1+{\int }_1^{n/2}{\displaystyle \frac{dx}{\lg (2x)}}\\ & =1+{\displaystyle \frac{1}{2}}{\int }_2^n{\displaystyle \frac{dx}{\lg x}}\\ & =1+{\displaystyle \frac{1}{2}}{\int }_2^{e^2}{\displaystyle \frac{dx}{\lg x}}+{\displaystyle \frac{1}{2}}{\int }_{e^2}^n{\displaystyle \frac{dx}{\lg x}}\end{array}$

当 $n$ 为奇数时，有

$\begin{array}{rl}T(n)& =\sum _{k=1}^{(n-1)/2}{\displaystyle \frac{1}{\lg (2k+1)}}\\ & ={\displaystyle \frac{1}{\lg 3}}+\sum _{k=2}^{(n-1)/2}{\displaystyle \frac{1}{\lg (2k+1)}}\\ & \le {\displaystyle \frac{1}{\lg 3}}+{\int }_1^{(n-1)/2}{\displaystyle \frac{dx}{\lg (2x+1)}}\\ & ={\displaystyle \frac{1}{\lg 3}}+{\displaystyle \frac{1}{2}}{\int }_3^n{\displaystyle \frac{dx}{\lg x}}\\ & ={\displaystyle \frac{1}{\lg 3}}+{\displaystyle \frac{1}{2}}{\int }_3^{e^2}{\displaystyle \frac{dx}{\lg x}}+{\displaystyle \frac{1}{2}}{\int }_{e^2}^n{\displaystyle \frac{dx}{\lg x}}\end{array}$

因此，令 ${\displaystyle c_0=max\{1+{\displaystyle \frac{1}{2}}{\int }_2^{e^2}{\displaystyle \frac{dx}{\lg x}},{\displaystyle \frac{1}{\lg 3}}+{\displaystyle \frac{1}{2}}{\int }_3^{e^2}{\displaystyle \frac{dx}{\lg x}}\}}$。那么可以写成

$$T(n)\le c+{\displaystyle \frac{1}{2}}{\int }_{e^2}^n{\displaystyle \frac{dx}{\lg x}}=c+{\displaystyle \frac{\ln 2}{2}}{\int }_{e^2}^n{\displaystyle \frac{dx}{\ln x}}$$

当 $n\ge e^2$ 时，不难得到不等式 $\ln n\le 2(\ln n-1)$。故此有

$\begin{array}{rl}T(n)& \le c+{\displaystyle \frac{\ln 2}{2}}{\int }_{e^2}^n{\displaystyle \frac{dx}{\ln x}}\\ & \le c+\ln 2\cdot {\int }_{e^2}^n{\displaystyle \frac{(\ln x-1)dx}{{\ln }^{2}x}}\\ & =c+\ln 2\cdot \left({{\displaystyle \frac{x}{\ln x}}|}_{e^2}^n\right)\\ & =c+{\displaystyle \frac{n\cdot \ln 2}{\ln n}}-{\displaystyle \frac{e^2\cdot \ln 2}{2}}\end{array}$

因此综上所述，$T(n)=O\left({\displaystyle \frac{n}{\lg n}}\right).$

最终有 $T(n)=\mathrm{\Theta }\left({\displaystyle \frac{n}{\lg n}}\right).$

j

令 $U(n)={\displaystyle \frac{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)=\mathrm{\Theta }(\lg m)$。

回代到 $U$ 中，得到 $U(n)=\mathrm{\Theta }(\lg \lg n)$。

因此有 $T(n)=\mathrm{\Theta }(n\lg \lg n)$。

4-5

a

将一次项和常数项目全部分离出来，那么等式右边三项可以写成：

$\begin{array}{rl}& z=z\\ & z\mathcal{F}(z)=\sum _{i=0}^{\mathrm{\infty }}{F}_i{z}^{i+1}=\sum _{i=1}^{\mathrm{\infty }}{F}_{i-1}{z}^i=F_{0}z+\sum _{i=2}^{\mathrm{\infty }}{F}_{i-1}{z}^i\\ & z^2\mathcal{F}(z)=\sum _{i=0}^{\mathrm{\infty }}{F}_i{z}^{i+2}=\sum _{i=2}^{\mathrm{\infty }}{F}_{i-2}{z}^i\end{array}$

三项相加，得到 ${\displaystyle z+\sum _{i=2}^{\mathrm{\infty }}(F_{i-1}+F_{i-2})z^i=z+\sum _{i=2}^{\mathrm{\infty }}{F}_i{z}^i}$。

代入 $F_0=0,F_1=1$，最终这个式子可以写成 ${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{F}_i{z}^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)={\displaystyle \frac{z}{1-z-z^2}}$

由于 $\varphi ={\displaystyle \frac{1+\sqrt{5}}{2}},\hat{\varphi }={\displaystyle \frac{1-\sqrt{5}}{2}}$，那么得到 $\varphi \cdot \hat{\varphi }=-1,\varphi +\hat{\varphi }=1,\varphi -\hat{\varphi }=\sqrt{5}$。

由于 $(1-\varphi z)(1-\widehat{\varphi z})=\varphi \cdot \hat{\varphi }\cdot z^2-(\varphi +\hat{\varphi })z+1=1-z-z^2$，因此 $\mathcal{F}(z)$ 还可以写成：$\mathcal{F}(z)={\displaystyle \frac{z}{(1-\varphi z)(1-\hat{\varphi }z)}}$

由于有如下变换：

$\begin{array}{rl}{\displaystyle \frac{1}{\sqrt{5}}}({\displaystyle \frac{1}{1-\varphi z}}-{\displaystyle \frac{1}{1-\hat{\varphi }z}})& ={\displaystyle \frac{1}{\sqrt{5}}}\left({\displaystyle \frac{(1-\hat{\varphi }z)-(1-\varphi z)}{(1-\varphi z)(1-\hat{\varphi }z)}}\right)\\ & ={\displaystyle \frac{1}{\sqrt{5}}}\left({\displaystyle \frac{\varphi -\hat{\varphi }}{(1-\varphi z)(1-\hat{\varphi }z)}}\right)\\ & ={\displaystyle \frac{1}{(1-\varphi z)(1-\hat{\varphi }z)}}\end{array}$

因此 $\mathcal{F}(z)$ 还可以写成：$\mathcal{F}(z)={\displaystyle \frac{1}{\sqrt{5}}}({\displaystyle \frac{1}{1-\varphi z}}-{\displaystyle \frac{1}{1-\hat{\varphi }z}})$.

c

$\begin{array}{rl}\mathcal{F}(z)& ={\displaystyle \frac{1}{\sqrt{5}}}({\displaystyle \frac{1}{1-\varphi z}}-{\displaystyle \frac{1}{1-\hat{\varphi }z}})\\ & ={\displaystyle \frac{1}{\sqrt{5}}}(\sum _{i=0}^{\mathrm{\infty }}{\varphi }^i{z}^i-\sum _{i=0}^{\mathrm{\infty }}{\hat{\varphi }}^i{z}^i)\\ & ={\displaystyle \frac{1}{\sqrt{5}}}\sum _{i=0}^{\mathrm{\infty }}({\varphi }^i-{\hat{\varphi }}^i)z^i\end{array}$

d

由题目 c 得到的等式，代入题目求和项中的 $F_i$，有 $F_i={\displaystyle \frac{{\varphi }^i-{\hat{\varphi }}^i}{\sqrt{5}}}={\displaystyle \frac{{\varphi }^i}{\sqrt{5}}}-{\displaystyle \frac{{\hat{\varphi }}^i}{\sqrt{5}}}$。

可以发现，对于 $\mathrm{\forall }i\ge 0,\left|{\displaystyle \frac{{\hat{\varphi }}^i}{\sqrt{5}}}\right|<0.5$ 均成立。因此，$F_i^{\prime }={\displaystyle \frac{{\hat{\varphi }}^i}{\sqrt{5}}}$ 最接近的整数即为 $F_i$。

e

考虑式子 $F_{i+2}-{\varphi }^i$ 的值。那么有

$F_{i+2}-{\varphi }^i={\displaystyle \frac{1}{\sqrt{5}}}({\varphi }^{i+2}-{\hat{\varphi }}^{i+2})-{\varphi }^i={\displaystyle \frac{3\sqrt{5}-5}{10}}{\varphi }^i-{\displaystyle \frac{3\sqrt{5}-5}{10}}{\hat{\varphi }}^i={\displaystyle \frac{3\sqrt{5}-5}{10}}({\varphi }^i-{\hat{\varphi }}^i)$

由于 $\varphi >\hat{\varphi }$，因此 $F_{i+2}-{\varphi }^i\ge 0$，即有 $F_{i+2}\ge {\varphi }^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 描述。

// 子程序`TEST(c1, c2)`表示对芯片c1, c2进行测试的结果。用True表示全好的报告，用False表示存在1个芯片是坏的报告。
GET-GOOD(chips)
  if chips.size == 0
    return NIL
  else if chips.size == 1
    return chip[0]
  else if chips.size % 2 == 0
    let C be new array
    for i = 0 to chips.size - 1 by 2
      if TEST(chips[i], chips[i + 1]) == True
        INSERT(C, chips[i])
    return GET-GOOD(C)
  else
    // chips[0]是保留的那个芯片。
    let C be new array
    for i = 1 to chips.size - 1 by 2
      if TEST(chips[i], chips[i + 1]) == True
        INSERT(C, chips[i])
    now = GET-GOOD(C)
    if now == NIL
      return chips[0]
    else
      return now

因此在一轮测试中，需要进行 $\lfloor {\displaystyle \frac{n}{2}}\rfloor$ 次测试。在一轮测试完成后，最多剩下 $\lceil {\displaystyle \frac{n}{2}}\rceil$ 个芯片。

接下来说明：经过一轮的测试后，剩下的芯片仍然满足：好芯片仍然严格多于坏芯片。

可以知道，如果算法 GET-GOOD 传入的芯片中，好坏的个数相同，那么最终这个算法的递归终点将是第 2 行的 NIL。因为在第 7 行的 for 循环完成后，得到的 C 数组中，好芯片和坏芯片的个数仍然相同。最终随着递归的进行，每一对好坏芯片都将被抵消，最终找不到任何一个好芯片。

如果算法 GET-GOOD 传入的芯片中，好芯片要比坏芯片多，那么在这一轮测试中，假设芯片的个数为 $n$，那么考虑如下 $2$ 个情况：

如果 $n$ 是偶数，在这 ${\displaystyle \frac{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(\lfloor {\displaystyle \frac{n}{2}}\rfloor \right)+\lfloor {\displaystyle \frac{n}{2}}\rfloor$

根据主定理的第二个条件，不难得到 $T(n)=O(n)$。

d

由于找出一个好的芯片需要 $O(n)$ 次比较，那么使用这个好的芯片对其它芯片进行测试就能够找到所有好芯片，总共需要 $n-1$ 次比较。

因此，最终找到所有好芯片的次数为 $O(n)+n-1=\mathrm{\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)$ 是一个递增函数。因此，$\mathrm{\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]$ 都成立。

同理，可以得出 $\mathrm{\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{array}{rlrlrlrlr}& & 37& & 23& & \mathbf{29}& & 32\\ & & 21& & 6& & 7& & 10\\ & & 53& & 34& & 30& & 31\\ & & 32& & 13& & 9& & 6\\ & & 43& & 21& & 15& & 6\end{array}$

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 矩阵的定义矛盾。

因此 $\mathrm{\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 \cdots \le f(m)$。为了计算 $f(1),f(3),f(5),\dots ,f(2k+1)$ 的值，假设 $f(0)=1$，有：

$\begin{array}{rl}S(n,m)& =\sum _{i=1}^{m/2}(f(2i)-f(2i-2)+1)\\ & =f(m)-f(0)+m/2\\ & =O(n+m)\end{array}$

e

为了解决整个求解问题，可以写出 $S(m)=S(m/2)+T(n,m)$。

由于 $T(n,m)=O(n+m)$，那么可以假设 $T(n,m)\le an+bm$

$\begin{array}{rl}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+{\displaystyle \frac{bm}{2^i}}\\ & =bm+an\lg m\end{array}$

因此 $S(m)=O(m+n\lg m)$。