CLRS 第一部分

练习

3.2-4

$\lceil\lg n\rceil! =\Omega((\frac{\lg n}{e})^{\lg n})$，而若 $\lceil\lg n\rceil!$ 多项式有界，则存在常数 $C$ 满足 $\lceil\lg n\rceil! =O(C^{\lg n})$，相互矛盾。因此 $\lceil\lg n\rceil!$ 多项式无界；

$\lceil \lg\lg n\rceil! =O(\lceil\lg\lg n \rceil^{\lceil\lg\lg n \rceil})=O(2^{\lg\lceil\lg\lg n \rceil\cdot\lceil\lg\lg n \rceil})$。其中，$\lg\lceil\lg\lg n \rceil<\lceil\lg\lg n \rceil=o(\sqrt{\lg n})$，因此 $\lceil \lg\lg n\rceil! =2^{o(\lg n)}$ 是多项式有界的。

3.2-5

$\lg^*(\lg n)=(\lg^*n)-1>\lg(\lg^*n)$。

4.2-2

4.2-3

令 $N=2^{\lceil\lg n\rceil}\in[n,2n)$。通过补 0 将矩阵维数扩展到 $N$，运行时间为 $\Theta(N^{\lg 7})=\Theta(n^{\lg 7})$。

4.2-5

基于矩阵分块乘法，

方法	运行时间递归式	渐进运行时间
用 132464 次乘法操作完成 $68\times 68$ 的矩阵相乘	$T(n)=132464T(n/68)$	$\Theta(n^{\log_{68}132464})$
用 143640 次乘法操作完成 $70\times 70$ 的矩阵相乘	$T(n)=143640T(n/70)$	$\Theta(n^{\log_{70}143640})$
用 155424 次乘法操作完成 $72\times 72$ 的矩阵相乘	$T(n)=155424T(n/72)$	$\Theta(n^{\log_{72}155424})$

4.2-7

4.5-5

令 $f(n)=n^{\log_b a}\cdot (b+1)^{\lceil\log_{b+1}n\rceil}=\Theta(n^{\log_b a+1})$。对于任意 $m$，令 $t=\lceil\log_{b+1}m\rceil$，总是存在 $n=(b+1)^t>m$，$af(n/b)=n^{\log_b a+1}=f(n)$，即不存在 $c<1$ 使得 $af(n/b)\le cf(n)$。

5.1-2

期望运行时间是 $\Theta(\frac{2^{\lceil\lg(b-a+1)\rceil}}{b-a+1}\lg(b-a+1))$。

5.1-3

期望运行时间是 $\Theta(\frac{1}{p(1-p)})$。

5.2-2

记事件 $A$ 为恰有两人被聘用，$B_i(i\in(1,n])$ 为除了 1 以外只有 $i$ 被聘用。若 $B_i$ 发生，则 $i$ 第一个应聘，且 2 到 $i-1$ 的所有人在 1 之后应聘，因此 $\mathrm{Pr}\{B_i\}=\frac{1}{n(i-1)}$。$\mathrm{Pr}\{A\}=\sum_{i=2}^n\mathrm{Pr}\{B_i\}=\frac{1}{n}\sum_{i=1}^{n-1}\frac{1}{i}$。

5.3-3

使用这种随机化方法，结果为某一特定排列的概率为 $\frac{k}{n^n}$，其中 $k$ 为整数，若这种方法能产生一个均匀随机排列，$\frac{k}{n^n}=\frac{1}{n!}$，即 $kn! =n^n$，而 $n>2$ 时，$n!$ 不是 $n^n$ 的因子，因此 $n>2$ 时这种方法不能产生均匀随机排列。

5.3-5

$n$ 个 $1\sim n^3$ 的随机数互不相同的概率为 $$\frac{n^3}{n^3}\times\frac{n^3-1}{n^3}\times\cdots\times\frac{n^3-n+1}{n^3}$$ 对于 $k\in[0,n)$， $$\frac{n^3}{n^3-k}-\frac{n^2-k-1}{n^2-k}=\frac{n^3+n^2k-k^2}{n^3(n^2-k)}>0$$ 因此 $$\begin{aligned} &\frac{n^3}{n^3}\times\frac{n^3-1}{n^3}\times\cdots\times\frac{n^3-n+1}{n^3}\\ >&\frac{n^2-1}{n^2}\times\frac{n^2-1}{n^2-1}\times\cdots\times\frac{n^2-n}{n^2-n+1}\\ =&1-\frac{1}{n} \end{aligned}$$

5.3-6

把结果中优先级相同的元素抽取出来，递归地随机排列，再按顺序放回原处。

5.4-4

假设一年有 $n$ 天。记 $k$ 个人中存在三个人生日相同为事件 $A_k$，$k$ 个人中有 $p(2p\le k)$ 对人生日相同，除此之外都两两不同为事件 $B_{kp}$。 $$\begin{aligned} \mathrm{Pr}\{B_{kp}\}&=\frac{1}{p!}\times\binom{k}{2}\times\binom{k-2}{2}\times\cdots\times\binom{k-2p+2}{2}\times\frac{n}{n}\times\frac{n-1}{n}\times\cdots\times\frac{n-k+p}{n}\times\frac{1}{n^p}\\ &=\frac{k!\times n!}{p!\times (k-2p)!\times 2^p\times n^k\times (n-k+p)!}\\ \mathrm{Pr}\{A_k\}&=1-\sum_{i=0}^{2i\le k}\mathrm{Pr}\{B_{ki}\}\\ &=1-\sum_{i=0}^{2i\le k}\frac{k!\times n!}{i!\times (k-2i)!\times 2^i\times n^k\times (n-k+i)!} \end{aligned}$$ 带入 $n=365$ 和 $\mathrm{Pr}\{A_k\}\ge 0.99$，$k$ 最小为 $155$。

5.4-7

$$A_{i,\lg n-2\lg\lg n}=1/2^{\lg n-2\lg\lg n}=\frac{\lg^2 n}{n}$$ 将序列分为 $\lfloor\frac{n}{\lg n-2\lg\lg n}\rfloor$ 个不相交的组，每个组都不是长度为 $\lg n-2\lg\lg n$ 的特征序列的概率是 $$\begin{aligned} &(1-\frac{\lg^2 n}{n})^{\lfloor\frac{n}{\lg n-2\lg\lg n}\rfloor}\\ \le&(1-\frac{\lg^2 n}{n})^{\frac{n}{\lg n-2\lg\lg n}-1}\\ \le&(1-\frac{\lg^2 n}{n})^{\frac{n}{\lg n}}\\ \le&(e^{-\frac{\lg^2 n}{n}})^{\frac{n}{\lg n}}=\frac{1}{n} \end{aligned}$$ 因此不出现比 $\lg n-2\lg\lg n$ 更长的特征序列的概率小于 $\frac{1}{n}$。

思考题

2-4

3. $T(n)=\Theta(n+inversion)$。回顾插入排序，外层循环每执行一次，逆序对数减少 $t_j$，最终逆序对数减少为 0，因此 $inversion=\sum_{j=0}^{n-1} t_j$；
4. 

3-6

我们只讨论 $n>c$ 的情况。

5. $f^*_2(n)=\lceil\lg\lg n\rceil$；
7. $f^*_2(n)=\lceil\log_3\lg n\rceil$；

8. 令 $g(n)=\lg n-\lg\lg n$，有 $f^*_2(n)=g^*_1(\lg n)$。显然，$g^*_1(n)\ge\lceil\frac{n-1}{\lg n}\rceil$。

   令 $t=g^*_1(n)$，我们知道，$t$ 是满足 $\lg g^0(n)+\lg g^1(n)+\cdots+\lg g^{t-1}(n)\ge n-1$ 的最小整数。函数 $x/g(x)$ 在 $(e,+\infty)$ 上单调递增，且 $g^{t-1}(n)>e$，因此对于 $i\in[0,t-3]\cap\mathbb{Z}$，$\lg g^i(n)-\lg g^{i+1}(n)<\lg g^{i+1}(n)-\lg g^{i+2}(n)$，即 $\lg g^i(n)>\frac{t-i-1}{t-1}\lg n$。若 $t\ge 2\frac{n-1}{\lg n}$，则 $\lg g^0(n)+\lg g^1(n)+\cdots+\lg g^{t-2}(n)>\frac{t}{2}\lg n\ge n-1$，与 $t$ 是最小满足条件的整数矛盾，因此 $t<\lfloor 2\frac{n-1}{\lg n}\rfloor$。

   综上所述，$f^*_2(n)\in[\lceil\frac{\lg n-1}{\lg\lg n}\rceil,\lfloor 2\frac{\lg n-1}{\lg\lg n}\rfloor)$。

4-4

1. $$\begin{aligned} &[z^i]F(z)=F_i\\ &\begin{aligned} [z^i](z+zF(z)+z^2F(z))&= \begin{cases} 1 & i=0\\ F_0 & i=1\\ F_{i-2}+F_{i-1} & i\ge 2 \end{cases}\\ &=F_i \end{aligned} \end{aligned}$$
2. 由 a 可知，$(1-z-z^2)F(z)=z$，因此 $$F(z)=\frac{z}{1-z-z^2}=\frac{z}{(1-\phi z)(1-\hat{\phi}z)}=\frac{1}{\sqrt{5}}(\frac{1}{1-\phi z}-\frac{1}{1-\hat{\phi}}z)$$
3. $$\begin{aligned} \frac{1}{1-\phi z}&=\sum_{i=0}^{+\infty}\phi^iz^i\\ \frac{1}{1-\hat{\phi}z}&=\sum_{i=0}^{+\infty}\hat{\phi}^iz^i \end{aligned}$$ 因此 $$F(z)=\sum_{i=0}^{+\infty}\frac{1}{\sqrt{5}}(\phi^i-\hat{\phi}^i)z^i$$
4. 由 c 可知，$F_i=\frac{1}{\sqrt{5}}(\phi^i-\hat{\phi}^i)$，因为 $F_i$ 是整数且 $\frac{1}{\sqrt{5}}\hat{\phi}^i<\frac{1}{2}$，所以 $F_i$ 为 $\frac{1}{\sqrt{5}}\phi^i$ 舍入到最近的整数。

4-5

1. 坏芯片选择一个所有坏芯片的子集，子集内部的芯片互相报告为好芯片，同时将子集外的芯片报告为坏芯片，这时从结果来看，这个子集内的坏芯片和好芯片是完全等价的；
2. • 将 $n$ 个芯片分为 $\lfloor\frac{n}{2}\rfloor$ 对，若 $n$ 为奇数则有一个芯片 $C$ 不在任何一对里；
   • 对这 $\lfloor\frac{n}{2}\rfloor$ 对芯片依次检测，若两个芯片都报告对方是好的，则任意抛弃一个，否则将两个芯片都抛弃；
   • 若 $n$ 为奇数且除了 $C$，存在其他芯片未被抛弃，则抛弃 $C$。
   这一过程之后芯片数量减少到至多 $\lfloor\frac{n}{2}\rfloor$ 个，同时好芯片数量超过一半的性质依然存在。
3. 最坏情况下的比较次数 $$T(n)=\begin{cases} 0 & n=1\\ T(\lfloor\frac{n}{2}\rfloor)+\lfloor\frac{n}{2}\rfloor & n\ge 2 \end{cases}$$ 一方面，$T(n)\ge\lfloor\frac{n}{2}\rfloor=\Omega(n)$，另一方面，对 $T(n)$ 使用数学归纳法，假设对于所有 $m<n$ 都有 $T(m)\le m$ 成立，$T(n)\le \lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{2}\rfloor\le n$，因此 $T(n)=O(n)$。综上，$T(n)=\Theta(n)$。

4-6

1. 必要性是显然的，我们来讨论充分性。

   条件变形得到 $A[i][j]-A[i][j+1]\le A[i+1][j]-A[i+1][j+1]$，由不等式的传递性，对于 $k>i$，$A[i][j]-A[i][j+1]\le A[k][j]-A[k][j+1]$。再次变形得到 $A[i][j]-A[k][j]\le A[i][j+1]-A[k][j+1]$，由不等式的传递性，对于 $i<k,j<l$，$A[i][j]-A[k][j]\le A[i][l]-A[k][l]$，即 $A[i][j]+A[k][l]\le A[k][j]+A[i][l]$；
3. 记该 Monge 矩阵为 $M$。因为 $M$ 是 Monge 矩阵，对于 $j<k$，$M[i][j]-M[i][k]\le M[i+1][j]-M[i+1][k]$。假设存在 $i\in[1,m)$，$f(i)>f(i+1)$，由于 $M[i+1][f(i+1)]$ 是第 $i+1$ 行的最左最小值，$M[i+1][f(i+1)]-M[i+1][f(i)]\le 0$，因此 $M[i][f(i+1)]-M[i][f(i)]\le 0$，与 $M[i][f(i)]$ 是第 $i$ 行的最左最小值矛盾，因此 $f(1)\le f(2)\le\cdots f(m)$；
4. 
5. $T(m,n)=T(\lfloor\frac{m}{2}\rfloor, n)+\Theta(m+n)=\Theta(m+n\log m)$

5-1

1. 记事件 $A_{tx}$ 为进行 $\mathrm{INCREMENT}$ 操作 $t$ 次后 $i=x$。 $$\begin{aligned} &\mathrm{Pr}\{A_{tx}\}=(1-\frac{1}{n_{x+1}-n_x})\mathrm{Pr}\{A_{t-1,x}\}+\frac{1}{n_x-n_{x-1}}\mathrm{Pr}\{A_{t-1,x-1}\}\\ &\begin{aligned} E[i_t]&=\sum_{x=1}^{+\infty}\mathrm{Pr}\{A_{tx}\}\times n_x\\ &=\sum_{x=1}^{+\infty}\left((1-\frac{1}{n_{x+1}-n_x})\times\mathrm{Pr}\{A_{t-1,x}\}\times n_x+\frac{1}{n_x-n_{x-1}}\times\mathrm{Pr}\{A_{t-1,x-1}\}\times n_x\right)\\ &=\sum_{x=1}^{+\infty}\left((1-\frac{1}{n_{x+1}-n_x})\times\mathrm{Pr}\{A_{t-1,x}\}\times n_x+\frac{1}{n_{x+1}-n_x}\times\mathrm{Pr}\{A_{t-1,x}\}\times n_{x+1}\right)\\ &=\sum_{x=1}^{+\infty}(n_x+1)\mathrm{Pr}\{A_{t-1,x}\}=E[i_{t-1}]+1 \end{aligned} \end{aligned}$$ 因此 $E[i_t]=t$。
2. 因为 $n_i=100i$，所以每次执行 $\mathrm{INCREMENT}$ 时，计数器有 $1/100$ 的概率增加 1。因此 $$\begin{aligned} &\mathrm{Pr}\{A_{tx}\}=\binom{t}{x}\frac{1}{100}^x\frac{99}{100}^{t-x}\\ &\begin{aligned} D[i_n]&=\sum_{x=0}^n\mathrm{Pr}\{A_{nx}\}(n_x-E[i_n])^2\\ &=\sum_{x=0}^n\binom{n}{x}\frac{1}{100}^x\frac{99}{100}^{n-x}(100x-n)^2\\ &=\sum_{x=0}^n\binom{n}{x}\frac{1}{100}^x\frac{99}{100}^{n-x}\left(10000x(x-1)+(10000-200n)x+n^2\right)\\ &=n(n-1)+(100-2n)n+n^2=99n \end{aligned} \end{aligned}$$ 更一般的，$n_i=di$ 时 $D[i_n]=(d-1)n$。

5-2

6. 显然，最坏情形下 $\mathrm{DETERMINISTIC\text{-}SEARCH}$ 要访问 $n-k+1$ 个下标。平均情形下，记 $X$ 为算法访问的下标个数，事件 $A_i$ 为算法访问了 $A[1]$ 到 $A[i]$ 并且没有结束， $$\begin{aligned} &\mathrm{Pr}\{A_i\}=\frac{\binom{n-i}{k}}{\binom{n}{k}}\\ &\begin{aligned} E[X]&=1+\sum_{i=1}^{n-1}\mathrm{Pr}\{A_i\}\\ &=1+\frac{1}{\binom{n}{k}}\sum_{i=1}^{n-1}\binom{n-i}{k}\\ &=1+\frac{1}{\binom{n}{k}}\sum_{i=1}^{n-1}\binom{i}{k}\\ &=1+\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n+1}{k+1} \end{aligned} \end{aligned}$$