算法设计技巧与分析-课后作业

前言：本文为NUAA《算法设计技巧与分析》课程配套教材的课后作业，由于这本教材很难找到答案，所以Po上部分我自己以及老师的答案，仅供参考~

教材长啥样

第1章 算法分析基本概念

1.9 证明观察结论1.4

//InsertSort
for(int i=2;i<=n;i++)
	x=A[i];
	j=i-1;
	while(j>0 && A[j]>x)
		A[j+1]=A[j];
		j=j-1;
	A[j+1]=x;

对于for 循环内的while循环

• 当while循环都是因为A[j]>x不满足而跳出循环时，

  对于每一次for循环，其执行的

  赋值次数 = 1 (x=A[i]) + 比较次数 (A[j]>x) - 1 (最后一次比较没有赋值) + 1 (A[j+1]=x)

  ​ = 1 + 比较次数

  而for循环执行了n-1次，因此这种情况下，总元素赋值次数= n-1 + 总元素比较次数

• 当while循环是因为j>0不满足而跳出循环时，此结论并不成立

1.17 BUBBLESORT

• 元素的最少比较次数是$n-1$次，在非降序排列时达到最小值
• 元素的最多比较次数是$\frac{n(n-1)}{2}$次，在非升序排列时达到最大值
• 元素的最少赋值次数是$0$次，在非降序排列时达到最小值
• 元素的最多赋值次数是$\frac{3n(n-1)}{2}$次，在非升序排列时达到最大值
• $T=O(n^2),T=\Omega(n)$
• 不可以用$\Theta$符号来表示，因为该算法的运行时间由线性到平方排列，不能精确表示

1.20 证明$\sum_{j=1}^{n}j^k=O(n^{k+1}),\sum_{j=1}^{n}j^k=\Omega(n^{k+1})\rightarrow\sum_{j=1}^{n}j^k=\Theta(n^{k+1})$

证明：

$$\sum_{j=1}^{n}j^{k}=1^k+2^k+3^k+...+n^k<=n^k+n^k+n^k+...+n^k=n\cdot n^k=n^{k+1}$$

因此$\sum^{n}_{j=1}j^k=O(n^{k+1})$

而

$$\begin{align*}\sum_{j=1}^{n}j^k&=1^k+2^k+3^k+...+\lfloor{\frac{n}{2}}\rfloor ^{k}+...+(\lfloor{\frac{n}{2}}\rfloor+1) ^{k}+...+n^{k} \\ &>=\underbrace{(\frac{n}{2})^k+...+(\frac{n}{2})^k}_{\lfloor \frac{n}{2}\rfloor}= \lfloor \frac{n}{2}\rfloor(\frac{n}{2})^{k}\end{align*}$$

即$\sum^{n}_{j=1}j^k=\Omega(n^{k+1})$

因此$\sum^{n}_{j=1}j^k=\Theta(n^{k+1})$

1.29 给出增长率次序

$$(\frac{1}{2})^n\prec 5\prec loglogn\prec log n^{100}\prec log^2n \prec n^{\frac{1}{100}} \prec \sqrt{n}\prec nlog n\prec {\color{red}(\sqrt{n})^{n}\prec n!}\prec2^{n^2}$$

---

$$\begin{align*}lim_{n\rightarrow\infty}\frac{n!}{\sqrt{n}^n}&=lim_{n\rightarrow\infty}\frac{\sqrt{2\pi n}(\frac{n}{e})^n}{n^{n/2}}\\&=lim_{n\rightarrow\infty}\sqrt{2\pi n}e^{-n}n^{n/2}\\&=lim_{n\rightarrow\infty}\sqrt{2\pi n}(\frac{n}{e^2})^{n/2}=\infty\end{align*}$$

1.32 考虑算法COUNT6，输入正整数n

• （a）第6步执行次数为

  $$\begin{align*}6\sum_{i=1}^{\lfloor log n\rfloor}i^2 &= 6\cdot \frac{(\lfloor logn\rfloor)(\lfloor logn\rfloor+1)(2\lfloor logn\rfloor+1)}{6} \\&=(\lfloor logn\rfloor)(\lfloor logn\rfloor+1)(2\lfloor logn\rfloor+1)\end{align*}$$

• （b）用$\Theta$更合适，因为

  $$\begin{align*}\lfloor logn \rfloor^3<=\lfloor logn\rfloor(\lfloor logn\rfloor+1)(2\lfloor logn\rfloor+1)<=3\lfloor logn \rfloor^3\end{align*}$$

  即$\lfloor logn\rfloor(\lfloor logn\rfloor+1)(2\lfloor logn\rfloor+1)=\Theta (\lfloor logn \rfloor^3)$

• （c）是$\Theta (\lfloor logn \rfloor^3)$

1.35 设计一个算法，找出存储在数组A[1…n]中的n个整数的最大值和最小值，使得它的时间复杂度分别是（a）$O(n)$ （b）$\Omega(nlog n)$

1. $O(n)$

   maxnum = A[1]
   minnum = A[1]
   for i=2 to n
   		if (A[i] > maxnum) then maxnum = A[i]
   		if (A[i] < minnum) then minnum = A[i]
   end for

   该算法的迭代次数为$n-1$，故时间复杂度为$O(n)$

2. $\Omega(nlogn)$

   BOTTOMUPSORT(A,1,n)
   maxnum = A[n]
   minnum = A[1]

   BOTTOMUPSORT的时间复杂度为$\Theta(nlogn)$，因此该算法的时间复杂度也为$\Omega(nlogn)$

1.38 设计算法在给定时间复杂度下求$a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$的值

假设数组$A[0,1,2,...,n]$存放$a_0,a_1,...,a_n$

1. $\Omega(n^2)$

   sum = A[0]
   for i=1 to n
   		temp = 1
   		for j=1 to i
   				temp = temp * x
   				j = j + 1
   		end for
   		sum = sum + A[i] * temp
   		i = i + 1
   end for

   该算法的迭代次数为$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$，故时间复杂度为$\Omega(n^2)$

2. $O(n)$

   sum = 0
   for i=n to 0
   	sum = sum * x + A[i]
   	i = i - 1
   end for

   该算法的迭代次数为$n+1$，故时间复杂度为$O(n)$

1.39 设计算法将具有n (n为偶数) 个正整数的集合S划分为有$\frac{n}{2}$个数的集合S1和S2，且S1中所有元素的和与S2中所有元素的和差值最大。

算法如下：

BOTTOMUPSORT(S,1,n)
for i=1 to n/2
	S1[i] = S[i]
end for
for i=n/2 to n
	S2[i-n/2+1] = S[i]
end for

该算法首先对S进行BOTTOMUPSORT排序（升序），将排序后的S前n/2个元素赋值给S1，后n/2个元素赋值给S2，此时S1中所有元素的和与S2中所有元素的和差值最大。

由于BOTTOMUPSORT的时间复杂度为$\Theta(nlogn)$，而后迭代$n$次，故总时间复杂度仍为$\Theta(nlogn)$

第2章 数学预备知识

A.12 用归纳法证明对于$n\ge 4,n!>2^n$

当$n=4$时，$4!=24>2^4=16$，该结论成立。

假设当$n=k$时，有此结论成立：

$$\begin{align*}k! &>2^k \\ 则 (k+1)k!&>(k+1)2^k >2\cdot2^k \\ 即 (k+1)!&>2^{k+1} \end{align*}$$

即对于$n=k+1$，该结论也成立。

因此对于$n\ge 4,n!>2^n$

A.17 分别用（a）代数方法（b）积分近似求和方法，证明$\sum_{j=1}^{n}log(\frac{n}{j})=O(n)$

1. 代数方法

   首先$\sum_{j=1}^{n}logj=\sum_{j=2}^{n}logj>=\int_{1}^{n}logxdx=nlogn-nloge+loge$

   $$\begin{align*}\sum_{j=1}^{n}log(\frac{n}{j})&=\sum_{j=1}^{n}logn-\sum_{j=1}^{n}logj\\ &=nlogn-\sum_{j=1}^{n}logj\\ &\le nlogn-(nlogn-nloge+loge)\\&=nloge-loge\end{align*}$$

   因此$\sum_{j=1}^{n}log(\frac{n}{j})=O(n)$

   ---

   更正：

   $${n!\ge e(\frac{n}{e})^n}\\ log\frac{n^n}{n!}\le loge^{n-1}=(n-1)loge$$

2. 积分近似求和方法

由于$f(x)=log(\frac{n}{x})$是递减的，有

$$\begin{align*} \sum_{j=1}^{n}log(\frac{n}{j})=logn+\sum_{j=2}^{n}log(\frac{n}{j})<=logn+\int_{1}^{n}log(\frac{n}{x}) dx \end{align*}$$

即

$$\sum_{j=1}^{n}log(\frac{n}{j})<=(n-1)loge$$

因此$\sum_{j=1}^{n}log(\frac{n}{j})=O(n)$

A.18 求解递推关系

1. $f(n)=2f(n-1)$，当$n\ge1$；$f(0)=2$

   由于

   $$\begin{align*}f(n)&=2f(n-1)\\&=2(2f(n-2))\\&=...\\&=2^{n}f(0)\end{align*}$$

   即$f(n)=2^{n+1}$

2. $f(n)=5f(n-1)$，当$n\ge1$；$f(0)=1$

   由于

   $$\begin{align*}f(n)&=5f(n-1)\\&=5(5f(n-2))\\&=...\\&=5^{n}f(0)\end{align*}$$

   即$f(n)=5^{n}$

A.19 求解递推关系

1. $f(n)=6f(n-1)-8f(n-2),当n\ge 2;f(0)=1,f(1)=0$

   特征方程为$x^2-6x+8=0$，解为$x_1=2,x_2=4$.

   因此

   $$\begin{align*} f(n)=c_12^n+c_24^n \\ \begin{cases} {c_1+c_2=1} \\ {2c_1+4c_2=0} \end{cases}\\c_1=2,c_2=-1\end{align*}$$

   即$f(n)=2^{n+1}-4^{n}$

2. $f(n)=-6f(n-1)-9f(n-2),当n\ge 2;f(0)=3,f(1)=-3$

   特征方程为$x^2+6x+9=0$，解为$x_1=x_2=-3$.

   因此

   $$\begin{align*} f(n)&=c_1(-3)^n+c_2n(-3)^n \\ &\begin{cases} {c_1=3} \\ {-3c_1-3c_2=-3} \end{cases}\\&c_1=3,c_2=-2\end{align*}$$

   即$f(n)=(-1)^n3^{n+1}-2n(-3)^{n}=(-3)^n(3-2n)$

A.20 求解递推关系：$f(n)=2f(n-1)+n+4,当n\ge1;f(0)=4$

令$f(n)=2^{n}f'(n),f(0)=f'(0)=4$，则

$$\begin{align*}2^nf'(n)&=2\cdot2^{n-1}f'(n-1)+n+4 \\\Rightarrow f'(n)&=f'(n-1)+\frac{n+4}{2^n} \\\Rightarrow f'(n)&=f'(0)+\sum_{i=1}^{n}\frac{i+4}{2^i}=f'(0)+6-\frac{n+6}{2^n}\end{align*}$$

因此$f(n)=2^nf'(n)=2^nf'(0)+2^n\cdot6-n-6=2^{n+2}-n+6\cdot(2^n-1)$

A.23(1.47) 分别用展开法和定理1.3求解递推式：$f(n)=9f(n/3)+n^2,n>=2;f(1)=1$，n为3的幂

• 展开法：

  设$k=log_3n$

  $$\begin{align*}f(n)&=9f(n/3)+n^2 \\ &=9(9f(n/3^2)+n^2/3^2)+n^2 \\ &=9^2f(n/3^2)+2n^2 \\ &=9^2(9f(n/3^3)+n^2/3^4)+2n^2 \\ &=9^3f(n/3^3)+3n^2 \\ &=... \\ &=9^kf(n/3^k)+kn^2 \\ &=9^kf(1)+kn^2 \\ &=n^2+n^2log_3n\end{align*}$$

• 定理1.3：

  $d=1,a=9,c=3,b=1,x=2$

  由于$a=9=3^2=c^x$，因此$f(n)=bn^xlog_cn+dn^x=n^2log_3n+n^2$

A.26(1.50) 用代入法求解递推式的上界

$$f(n)=\begin{cases}f(\lfloor{n/4}\rfloor)+f(\lfloor{3n/4}\rfloor)+n,n\ge4\\4,n<4\end{cases}$$

用$O$符号表示解

解：

猜测对于某个$d>0$，有$f(n)\le dnlogn+4n$对于所有的$n\ge1$均成立。

因此对于$n\ge 4$，有

$$\begin{align*}f(n)&=f(\lfloor{n/4}\rfloor)+f(\lfloor{3n/4}\rfloor)+n\\ &\le d\lfloor\frac{n}{4}\rfloor log\lfloor\frac{n}{4}\rfloor+4\lfloor\frac{n}{4}\rfloor+d\lfloor\frac{3n}{4}\rfloor log\lfloor\frac{3n}{4}\rfloor+4\lfloor\frac{3n}{4}\rfloor+n\\ &\le d\frac{n}{4} log\frac{3n}{4}+d\frac{3n}{4} log\frac{3n}{4}+5n\\ &=dnlogn+\frac{3}{4}dnlog3-2dn+5n\end{align*}$$

为了证明$f(n)\le dnlogn+4n$，要让

$$\frac{3}{4}dnlog3-2dn+n\le 0$$

即

$$d\ge\frac{1}{2-\frac{3}{4}log3}=1.23$$

显然当$n<4$时，$f(n)=4\le1.23nlogn+4n$

因此$f(n)=O(nlogn)$

A.31(1.55) 用更换变元法求解递推式的渐进表现

$$f(n)=\begin{cases}f(n/2)+\sqrt{n},n\ge4\\2,n<4\end{cases}$$

其中n具有形式$2^{2^k}$

解：设$n=2^{t},t=2^k$，则

$$f(2^t)=\begin{cases}f(2^{t-1})+\sqrt{2^{t}},2^t\ge4\\2,2^t<4\end{cases}$$

那么$g(t)=f(2^t),$则

$$g(t)=\begin{cases}g(t-1)+\sqrt{2^t},t\ge2\\2,t<2\end{cases}$$

因

$$\begin{align*}g(t)&=2^{t/2}+g(t-1)\\&=2^{t/2}+2^{(t-1)/2}+g(t-2)\\&=...\\&=(2^{t/2}+2^{(t-1)/2}...+2^{2/2})+g(1)\\&=2+\sum_{i=2}^{t}{2^{i/2}}=2+\frac{2^{(t+1)/2}-2}{\sqrt{2}-1},\ t\ge 2\end{align*}$$

将$n=2^t,t=log\ n$代入上式，得

$$f(n)=\begin{cases}(\sqrt{2}+1)\cdot (2^{(log\ 2n)/2}-2)+2,n\ge 4 \\2,n<4 \end{cases}$$

因此$f(n)=\Theta(\sqrt{2}^{log\ 2n})$

第4章 堆和不相交集数据结构

4.5(3.5) 编写算法判断给定数组A[1…n]是否是一个堆；给出其时间复杂性

isHeap = True
for i=1 to n/2
	if key(A[i]) < key(A[2*i]) 
		isHeap=False
		break
	if 2*i+1<=n and key(A[i] < key(A[2*i+1])
		isHeap=False
		break
return isHeap

由于该算法最多比较$\lfloor n/2\rfloor$次，因此该算法的时间复杂度为$\Theta(n)$

4.13(3.13) 设A[1…19]是一个有19个整数的数组，对其MAKEHEAP

• 调用几次过程SIFT-DOWN?

  $\lfloor19/2\rfloor=9$

  由于从9到1每次都要执行SIFT-DOWN函数，因此调用了9次过程SIFT-DOWN

• 元素交换的最大次数是多少？

  考虑第$i$个节点，其子节点为$2^i$，则最多可交换1次

  若子节点有子节点$2^2i$，则最多交换2次

  ……

  若…有子节点$2^ki$，最多交换k次

  因此有不等式$2^ki<=19$，对于以下i，求出其k：

  i=1 k=4

  i=2 k=3

  i=3-4 k=2

  i=5-9 k=1

  因此共最多交换4+3+4+5=16次

• 给出有19个元素的数组，需要以上所述的元素交换最大次数

  A[1…19]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

  即按升序排列的19个元素的数组

4.15(3.15)证明最坏情况下该建堆算法的运行时间是$\Theta(n\ log\ n)$。给定整数数组A[1…n]，建立A的堆B[1…n]：从空堆开始，反复将A中元素插入B，每一次调整当时的堆，直到B中包含A中所有的元素

考虑从1到n将元素插入B中，当插入第i个元素后：

此时堆中有i个元素，当前二叉堆的高度为$\lfloor log\ i\rfloor$

执行SIFT-UP操作需要的最多元素比较次数为$\lfloor log\ i\rfloor$，此为最坏情况

因此总共的元素比较次数为$\sum_{i=1}^{n}\lfloor log\ i\rfloor$=$\Theta(nlog\ n)$

4.19(3.19) 编写算法将两个相同大小的堆合并为一个，时间复杂性是多少？

设存在堆A[1…n]和堆B[1…n]，新堆为C[1…2n]

for i=1 to n
	C[i] = A[i]
for i=1 to n
	C[i+n] = B[i]
#执行堆化操作
for i=n downto 1
	SIFT-DOWN(C,i)

该算法首先将A中的元素和B中的元素复制到新堆C中，再对C进行堆化操作

复制的次数为$2n$，堆化的时间复杂度为$\Theta(n)$，因此总时间复杂度为$\Theta(n)$

4.22(3.22) 对于d堆的情况，重写SIFT-DOWN，以d和n为测度，它的时间复杂度是多少？

对于d堆，规定以下函数中变量d为其堆数，数组A[1..n]存储此堆

• 获取节点i的父节点位置的函数如下：

def d-ARY-PARENT(i)
	return floor((i - 2) / d + 1)

• 获取节点i的子节点位置的函数如下：

  其中d-ARY-CHILD(i, j)表示节点i的第j个孩子，且$1\le j\le d$

def d-ARY-CHILD(i, j)
  return d*(i − 1) + j + 1

• SIFT-DOWN如下

def SIFT-DOWN(i)
	done=False
	if d-ARY-CHILD(i, 1)>n
		return
	while(1)
		i=d-ARY-CHILD(i, 1)
		for j=1 to d-1
			if i+j<=n and key(A[i+j])>key(A[i])
				i=i+j
		if key(A[i])>key(A[d-ARY-PARENT(i)])
			swap(A[i],A[d-ARY-PARENT(i)])
		else done=True
		if done or d-ARY-CHILD(i, 1)>n
			break

由于此d堆的高度最多为$\lfloor log_dn\rfloor$，每一次下移都会遍历$d$个子节点，因此时间复杂度为$O(d\ log_d\ n)$

第5章 归纳法

5.1(4.1) 给出一个计算第n个Fibonacci数$f_n$的递归算法

$$f_1=f_2=1;f_n=f_{n-1}+f_{n-2},对于 n\ge 3$$

def GetFibonacci(n):
	if n==1 or n==2
		return 1
	else
		return GetFibonacci(n-1)+GetFibonacci(n-2)

5.2(4.2) 给出一个计算第n个Fibonacci数$f_n$的迭代算法

nfib=0
fn_1=fn_2=1
if n<3
	nfib=1
else
	for i=3 to n
		nfib=fn_1+fn_2
		fn_1=fn_2
		fn_2=nfib
	endfor
return nfib

5.3(4.3) 用归纳法设计一个递归算法，在有n个元素的序列A[1…n]中寻找最大元素

def SearchMaxElem(left,right):
	if right==left:
		return A[left]
	else:
		return max(A[right],SearchMaxElem(left,right-1))

SearchMaxElem(1,n)

5.14(4.14) 用EXPREC计算

$(a)2^5\ \ (b)2^7\ \ (c)3^5\ \ (d)\ \ 5^7$

1. $2^5$

   $2^5=2\cdot(2^2)^2=2\cdot(2\cdot2)^2=32$

2. $2^7$

   $2^7=2\cdot(2^3)^2=2\cdot(2\cdot(2)^2)^2=128$

3. $3^5$

   $3^5=3\cdot(3^2)^2=3\cdot(3\cdot3)^2=243$

4. $5^7$

   $5^7=5\cdot(5^3)^2=5\cdot(5\cdot(5)^2)^2=78125$

5.15(4.15) 用算法EXP代替算法EXPREC计算5.14

1. $2^5$

   $5=101B$

   初始时y=1

   第一次循环j=2：$y=y^2=1,d_2=1\rightarrow y=xy=2$

   第二次循环j=1：$y=y^2=4,d_1=0$

   第三次循环j=0：$y=y^2=16,d_0=1\rightarrow y=xy=32$

   因此$2^5=y=32$

2. $2^7$

   $7=111B$

   初始时y=1

   第一次循环j=2：$y=y^2=1,d_2=1\rightarrow y=xy=2$

   第二次循环j=1：$y=y^2=4,d_1=1\rightarrow y=xy=8$

   第三次循环j=0：$y=y^2=64,d_0=1\rightarrow y=xy=128$

   因此$2^7=y=128$

3. $3^5$

   $5=101B$

   初始时y=1

   第一次循环j=2：$y=y^2=1,d_2=1\rightarrow y=xy=3$

   第二次循环j=1：$y=y^2=9,d_1=0$

   第三次循环j=0：$y=y^2=81,d_0=1\rightarrow y=xy=243$

   因此$3^5=y=243$

4. $5^7$

   $7=111B$

   初始时y=1

   第一次循环j=2：$y=y^2=1,d_2=1\rightarrow y=xy=5$

   第二次循环j=1：$y=y^2=25,d_1=1\rightarrow y=xy=125$

   第三次循环j=0：$y=y^2=15625,d_0=1\rightarrow y=xy=78125$

   因此$5^7=y=78125$

5.29 用图说明算法MAJORITY对下列数组的运算

1. 5 7 5 4 5

   5	7	5	4	5
   candidate(1)		candidate(3)		candidate(5)
   cnt=1	cnt=0，退出循环	cnt=1	cnt=0，退出循环	j=5，返回5

   此时c=5,count=0

   5	7	5	4	5
   count=1	count=1	count=2	count=2	count=3

   由于$count=3>2$，返回多数元素c=5

2. 5 7 5 4 8

   5	7	5	4	8
   candidate(1)		candidate(3)		candidate(5)
   cnt=1	cnt=0，退出循环	cnt=1	cnt=0，退出循环	j=5，返回8

   此时c=8,count=0

   5	7	5	4	8
   count=0	count=0	count=0	count=0	count=1

   由于$count=1<2$，因此不存在多数元素

3. 2 4 1 4 4 4 6 4

   2	4	1	4	4	4	6	4
   candidate(1)		candidate(3)		candidate(5)
   cnt=1	cnt=0,退出循环	cnt=1	cnt=0,退出循环	cnt=1	cnt=2	cnt=1	cnt=2,j=8,退出循环

   此时c=4,count=0

   2	4	1	4	4	4	6	4
   count=0	count=1	count=1	count=2	count=3	count=4	count=4	count=5

   由于$count=5>4$，返回多数元素c=4

5.31 证明结论对错：如果算法MAJORITY的过程candidate的第7步中j=n但count=0，那么c是多数元素

该结论错误。下面给出反例：

对于仅有2个元素的数组$A[\ ]=\{a_1,a_2\},a_1\not = a_2$.

执行candidate算法：

a1	a2
candidate(1)
count=1	count=0

仅进行一次循环，此时j=2=n且count=0 ,c=a2 ，显然a2不是多数元素。

5.32 证明结论对错：如果算法MAJORITY的过程candidate的第7步中j=n但count>0，那么c是多数元素

该结论错误。下面给出反例：

对于仅有3个元素的数组$A[\ ]=\{a_1,a_2,a_3\},a_1\not = a_2\not =a_3$.

执行candidate算法：

a1	a2	a3
candidate(1)		candidate(3)
count=1	count=0	count=1

candidate(3)中j=n=3，并未进入循环，此时count=1>0 ,c=a3 ，显然a3不是多数元素。

第6章 分治

6.5 给出一个整数数组$A[1..n]$中求出所有元素和的分治算法，此算法应从把输入元素近似的划分为两半开始。算法所需的工作空间是多少？

输入：EleSum(1,n)

输出：A[1…n]的元素和

EleSum(left,right)
	if left==right
		return A[left]
	else 
		mid=(left+right)/2
		return EleSum(left,mid)+Elesum(mid+1,right)	

每次为mid申请$O(1)$的空间，而递归的深度为$logn$，因此所需空间为$\Theta(log\ n)$

6.2 考虑算法SLOWMINMAX,它是将算法MINMAX的检验条件if high-low=1修改为if high =low,并对此算法做一些相应改变而得出的。这样，在算法SLOWMINMAX中，当输入数组的大小为1时，递归停止。计算由此算法找出数组$A[1…n]$中的最大值和最小值所需的比较次数，这里n是2的幂。解释此算法的比较次数为什么大于算法MINMAX的比较次数[提示:在这种情形下，初始条件是C(1)=0]。

此时元素比较次数的递推式为

$$C(n)=\begin{cases}0,n=1\\ 2C(n/2)+2,n>1\end{cases}$$

求解此递推式，

$$\begin{align*}C(n)&=2C(n/2)+2\\&=4C(n/4)+4+2\\&=8C(n/8)+8+4+2\\&=...\\&=2^kC(n/2^k)+2^k+2^{k-1}+...+2\\&=2n-2\end{align*}$$

显然此时元素比较次数2n-2大于3n/2-2

因为此算法的递归终止条件和MINMAX 不同，递归深度更大

6.10 用算法MERGESORT进行排序

1. $32\quad15\quad14\quad15\quad11\quad17\quad25\quad51$

   $$[15\ 32]\quad[14\ 15]\quad[11\ 17]\quad[25\ 51] \\ \downarrow\\ [14\ 15\ 15\ 32]\quad[11\ 17\ 25\ 51]\\ \downarrow \\ [11\ 14\ 15\ 15\ 17\ 25\ 32\ 51]$$

2. $12\quad25\quad17\quad19\quad51\quad32\quad45\quad18\quad22\quad37\quad15$

$$[12]\quad[25]\quad[17]\quad[19]\quad[51]\quad[32]\quad[45]\quad[18]\quad[22]\quad[37]\quad[15]\\\downarrow\\ [12\ 25]\quad[17]\quad[19\ 51]\quad[32]\quad[45\ 18]\quad[22]\quad[37\ 15]\\\downarrow\\ [12\ 25]\quad[17\ 19\ 51]\quad[18\ 32\ 45]\quad[15\ 22\ 37]\\\downarrow\\ [12\ 17\ 19\ 25\ 51]\quad[15\ 18\ 22\ 32\ 37\ 45]\\\downarrow\\ [12\ 15\ 17\ 18\ 19\ 22\ 25\ 32\ 37\ 45\ 51]$$

6.13 列出一组数据，使其满足以下条件

1. BOTTOMUPSORT和MERGESORT 执行相同的元素比较次数

   数据：$A[1..n]=[8,7,2,1,6,5,4,3]$

   当$n=2^k$时，两种算法的递归树均一致，比较次数也一致

2. BOTTOMUPSORT执行的元素比较次数大于MERGESORT

   数据：$A[1..6]=\{1,2,3,4,5,6\}$

   $$[1\ 2 \ 3\ 4\ 5\ 6]\\\downarrow \\ [1\ 2\ 3\ 4]\quad [5\ 6]\\\downarrow\\ [1\ 2\ ]\quad [3\ 4]\quad [5\ 6]\\\downarrow\\ 1\quad 2\quad3\quad 4\quad 5\quad 6$$

   BOTTOMUPSORT执行比较次数为3+2+4=9次

   $$1\quad 2\quad 3\quad 4\quad\ 5\quad 6\\\downarrow \\ [1]\quad[2\ 3]\quad [4]\quad [5\ 6]\\ \downarrow\\ [1\ 2\ 3]\quad [4\ 5\ 6]\\\downarrow\\ [1\ 2\ 3\ 4\ 5\ 6]$$

   MERGESORT执行比较次数为2+2+3=7次

3. BOTTOMUPSORT执行的元素比较次数小于MERGESORT

   数据：$A[1..5]=\{5,4,3,2,1\}$

   BOTTOMUPSORT执行比较次数为2+2+1=5次

   MERGESORT执行比较次数为2+2+3=7次

6.17 用SELECT在例6.1的数据中找出第k小元素

$A[]=\{8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7\}$

阈值为6：即当剩余元素≤6时直接排序并返回A[k]

1. k=1

   划分为5组：

   $\{8,33,17,51,57\},\{49,35,11,25,37\},\{14,3,2,13,52\},\{12,6,29,32,54\},\{5,16,22,23,7\}$每组升序取中项：$\{33,35,13,29,16\}$

   递归求中项元素：$mm=29$

   将A划分为3组：

   $\{8,17,11,25,14,3,2,13,12,6,5,16,22,23,7\},\{29\},\{33,51,57,49,35,37,52,32,54\}$由于1<15=|A1|，递归对A1求解：

   划分为3组：$\{8,17,11,25,14\},\{3,2,13,12,6\},\{5,16,22,23,7\}$

   每组升序取中项集合：$\{14,6,16\}$,$mm=14$

   将A划分为3组：$\{8,11,3,2,13,12,6,5,7\},\{14\},\{17,25,16,22,23\}$

   由于1<9=|A1|，递归对A1求解：

   划分为1组：$\{8,11,3,2,13\}$

   升序取中项：mm=8

   将A划分为3组：$\{3,2\},\{8\},\{11,13\}$

   由于1<2=|A1|，递归对于A1求解：

   只剩2个元素，小于阈值，直接排序求解A[k]=A[1]=2

2. k=9

   根据上问，将A划分为3组：

   $\{8,17,11,25,14,3,2,13,12,6,5,16,22,23,7\},\{29\},\{33,51,57,49,35,37,52,32,54\}$由于9<15=|A1|，递归对A1求解：

   划分为3组：$\{8,17,11,25,14\},\{3,2,13,12,6\},\{5,16,22,23,7\}$

   每组升序取中项：$\{14,6,16\}$,$mm=14$

   将A划分为3组：$\{8,11,3,2,13,12,6,5,7\},\{14\},\{17,25,16,22,23\}$

   由于9=9=|A1|，递归对A1求解：

   划分为2组：$\{8,11,3,2,13\},\{12,6,5,7\}$

   每组升序取中项集合：$\{8,6\}$，mm=6

   将A划分为3组：$\{3,2,5\},\{6\},\{8,11,13,12,7\}$

   由于k=9>4=|A1|+|A2|

   递归求解A3，k=k-|A1|-|A2|=5

   由于5<阈值6，直接排序后返回A[5]=13

3. k=17

   根据上问，将A划分为3组：

   $\{8,17,11,25,14,3,2,13,12,6,5,16,22,23,7\},\{29\},\{33,51,57,49,35,37,52,32,54\}$由于k=17>16=|A1|+|A2|，递归对A3求解，k=k-16=1

   将A=A3分为2组：$\{33,51,57,49,35\},\{37,52,32,54\}$

   取中项集合：$\{49,37\}$，mm=37

   划分为3组：$\{33,35,32\},\{37\},\{51,57,49,52,54\}$

   由于k=1<3=|A1|，递归对A1进行求解：

   由于只剩3个元素，直接排序求解A[k]=32

4. k=22

   根据上问，将A划分为3组：

   $\{8,17,11,25,14,3,2,13,12,6,5,16,22,23,7\},\{29\},\{33,51,57,49,35,37,52,32,54\}$由于k=22>16=|A1|+|A2|，递归对A3求解，k=k-16=6

   将A=A3分为2组：$\{33,51,57,49,35\},\{37,52,32,54\}$

   取中项集合：$\{49,37\}$，mm=37

   划分为3组：$\{33,35,32\},\{37\},\{51,57,49,52,54\}$

   由于k=6>4=|A1|+|A2|，递归对A3进行求解，k=k-4=2

   由于只剩5个元素，直接排序后求解：A[k]=51

5. k=25

   根据上问，将A划分为3组：

   $\{8,17,11,25,14,3,2,13,12,6,5,16,22,23,7\},\{29\},\{33,51,57,49,35,37,52,32,54\}$由于k=25>16=|A1|+|A2|，递归对A3求解，k=k-16=9

   将A=A3分为2组：$\{33,51,57,49,35\},\{37,52,32,54\}$

   取中项集合：$\{49,37\}$，mm=37

   划分为3组：$\{33,35,32\},\{37\},\{51,57,49,52,54\}$

   由于k=9>4=|A1|+|A2|，递归对A3进行求解，k=k-4=5

   由于只剩5个元素，直接排序后求解：A[k]=57

6.31 对于数组{27,13,31,18,45,16,17,53}，应用算法SPLIT进行处理

low=1，high=8，主元为A[1]=27，初始i=low=1

i=1, j=2: 13<27, i=2, j=2 不交换

$[27\quad 13\quad 31\quad 18\quad 45\quad 16\quad 17\quad 53]$

i=2, j=4: 18<27, i=3, j=4 交换

$[27\quad 13\quad 18\quad 31\quad 45\quad 16\quad 17\quad 53]$

i=3, j=6: 16<27, i=4, j=6 交换

$[27\quad 13\quad 18\quad 16\quad 45\quad 31\quad 17\quad 53]$

i=4, j=7: 17<27, i=5, j=7 交换

$[27\quad 13\quad 18\quad 16\quad 17\quad 31\quad 45\quad 53]$

结束后互换A[1]和A[5]

最终结果：$[17\quad 13\quad 18\quad 16\quad 27\quad 31\quad 45\quad 53]$

6.32 对于算法SPLIT，当算法以输入数组$A[1..n]$表示且不包括A[low]和A[i]的交换时，执行的元素比较次数设为$f(n)$

1. 对于什么样的$A[1..n]$，有$f(n)=0$

   首先，当$a_{2..n}> a_1$时，不会发生元素交换；

   而当i==j时也不会发生元素交换，也就是说存在下标k，

   $$A[1..n]={a_1,a_2,...,a_k,a_{k+1},...,a_n}$$

   $a2$到$a_k$均$\le a_1$，$a_{k+1}$到$a_n$均$>a_1$

2. $f(n)$最大值是什么，解释什么时候达到最大值

   $max(f(n))$=数组中不大于$a_1$的元素个数，当$a_2>a_1$时有最大值

6.36 用QUICKSORT对数组排序

1. $\{24,33,24,45,12,12,24,12\}$

   $$[12,24,12,12,24]\ [24]\ [33,45] \\ \downarrow\\ [12,12]\ [12]\ [24,24]\ [24]\ [33]\ [45]\\ \downarrow\\ [12]\ [12]\ [12]\ [24]\ [24]\ [24]\ [33]\ [45]$$

2. $\{3,4,5,6,7\}$

   $$[3]\ [4,5,6,7]\\ \downarrow\\ [3]\ [4]\ [5,6,7]\\ \downarrow\\ ...\\ \downarrow\\ [3]\ [4]\ [5]\ [6]\ [7]$$

3. $\{23,32,27,18,45,11,63,12,19,16,25,52,14\}$

$$[14,18,11,12,19,16]\ [23]\ [32,27,45,63,25,52]\\ \downarrow\\ [12,11]\ [14]\ [18,19,16]\ [23]\ [25,27]\ [32]\ [45,63,52]\\ \downarrow\\ [11]\ [12]\ [14]\ [16]\ [18]\ [19]\ [23]\ [25]\ [27]\ [32]\ [45]\ [52]\ [63]$$

6.45 写出传统的矩阵乘法算法

MatrixMulti(A[n][n],B[n][n]):
    for i=1 to n:
        for j=1 to n:
            for k=1 to n:
                C[i][j]= C[i][j]+A[i][k]*B[k][j]
	return C[n][n]

6.50 设计分治算法判断两个二叉树$T_1$和$T_2$是否等同

如果$T_1=T_2$，则$T_1.data=T_2.data、T_1.lchild=T2.lchild、T_1.rchild=T_2.rchild$

因此我们可以递归判断根节点值和左右子树是否相同

有3种情况：

1. 两个根节点同时为空

   此时返回True即可

2. 两个根节点都不为空

   此时判断值是否相同，且分别递归判断节点1和节点2的左/右子树是否相同

3. 一个为空、另一个不为空

   此时返回False即可

isBiTreeEqual(root1,root2)
	if(root1==NULL and root2!=NULL
      or root1!=NULL and root2==NULL)
    	return False
	else if(root1!=NULL and root2!=NULL)
    	return root1.data==root2.data and isBiTreeEqual(root1.left,root2.left) and isBiTreeEqual(root1.right,root2.right)
    else
    	return True

第7章 动态规划

7.5 用算法LCS找出A="xzyzzyx"和B="zxyyzxz"的最长公共子序列的长度，给出一个最长公共子序列

	A	x	z	y	z	z	y	x
B		0	0	0	0	0	0	0
z	0	0	1	1	1	1	1	1
x	0	1	1	1	1	1	1	2
y	0	1	1	2	2	2	2	2
y	0	1	1	2	2	2	3	3
z	0	1	2	2	3	3	3	3
x	0	1	2	2	3	3	3	4
z	0	1	2	2	3	4	4	4

长度为4，一个最长公共子序列：“xzzx”

7.6 说明如何修改算法LCS，使得它输出最长公共子序列

我们可以通过从$f[n][m]$逆向查找，找到其更新来源，就能找出所有的最长公共子序列

ans=set()
findLCS(i,j,str):
    while(i>0 and j>0)
    	if(a[i]==b[j])
        	str=str+a[i-1]
            i=i-1
            j=j-1
        else
        	if(f[i-1][j]>f[i][j-1])
            	i=i-1
            else if(f[i-1][j]<f[i][j-1])
            	j=j-1
            else
            	findLCS(i-1,j,str)
                findLCS(i,j-1,str)
                return
    ans.insert(str.reverse())

该算法中ans是存储最长公共子序列的集合

转移种类有：

1. $a[i]=b[j]$，则一定可以作为一个字符存进str中
2. $a[i]\not =b[j]\ and\ f[i-1][j]>f[i][j-1]$，则从$f[i-1][j]$转移而来
3. 当小于号同理
4. 如果两个相等，则说明可以从两边转移而来，因此需要有两个递归分支

7.7 如何修改算法LCS，使得它仅需要$\Theta (min\{m,n\})$的空间

由于每个状态$f[i][j]$的更新仅与$f[i-1][j-1]、f[i][j-1]、f[i-1][j]$有关，我们可以采用滚动数组实现LCS，这里不妨假定$1\le i\le n,1\le j\le m,m\le n$，即只保留$f[i]、f[i-1]$的值

f[2][m]
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        if(a[i]==b[j])
        	f[i%2][j]=f[(i-1)%2][j-1]+1;
		else
            f[i%2][j]=max(f[(i-1)%2][j],f[i%2][j-1])

$n\le m$时同理，这样空间复杂度为$2m=\Theta(min\{m,n\})$

7.9 用MATCHAIN计算矩阵相乘后如图所示，找出$C[1,5]$和执行乘法运算$M_1\times ...\times M_5$的最优括号表达式

$$C[1,5]=min \begin{cases} C[1,1]+C[2,5]+4\times5\times5=307 \\ C[1,2]+C[3,5]+4\times3\times5=252 \\ C[1,3]+C[4,5]+4\times6\times5=372 \\ C[1,4]+C[5,5]+4\times4\times5=260 \\ \end{cases} =252$$

最优表达式为$(M_1\times M_2)\times ((M_3\times M_4) \times M_5)$

7.12 给出三个矩阵的例子，它们的一种乘法顺序需要的数量乘法的次数至少是另一种顺序的100倍

矩阵如下：

$$M_1:100\times 1\ \ \ \ \ M_2:1\times 100\ \ \ \ \ M_3:100\times 1$$

顺序1：$(M_1\times M_2)\times M_3=100\times 1\times 100+100\times 100\times 1=20000$

顺序2：$M_1\times (M_2 \times M_3)=1\times 100\times 1+100\times 1\times 1=200$

因此顺序1的数量乘法次数是顺序2的100倍

7.21 求解背包问题：有4个体积是[2,3,5,6]，价值为[3,4,5,7]的物品，背包容量是11

$dp[i,j]$如下，其中$1\le i\le 4,1\le j\le 11$，$dp[i,j]$表示背包容量为$j$时，在前$i$个物品中选取物品的最大价值。

i\j	1	2	3	4	5	6	7	8	9	10	11
1	0	3	3	3	3	3	3	3	3	3	3
2	0	3	4	4	7	7	7	7	7	7	7
3	0	3	4	4	7	7	8	9	9	12	12
4	0	3	4	4	7	7	8	10	11	12	14

因此最大价值为14，选取的物品为1、2、 4

7.22 求解背包问题：有5个体积是[3,5,7,8,9]，价值为[4,6,7,9,10]的物品，背包容量是22

$dp[i,j]$如下，其中$1\le i\le 5,1\le j\le 22$，$dp[i,j]$表示背包容量为$j$时，在前$i$个物品中选取物品的最大价值。

i/j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
1	0	0	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
2	0	0	4	4	6	6	6	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
3	0	0	4	4	6	6	7	10	10	11	11	13	13	13	17	17	17	17	17	17	17	17
4	0	0	4	4	6	6	7	10	10	11	13	13	15	15	17	19	19	20	20	22	22	22
5	0	0	4	4	6	6	7	10	10	11	13	14	15	16	17	19	20	20	21	23	23	25

因此最大价值为25，选取的物品为2、4、5

7.24 说明如何修改算法KNAPSACK，使其只需$\Theta(C)$空间，$C$是背包容量

由于dp[i][j]中的i只和i-1有关，我们可以采用滚动数组的方式实现，此时对于背包容量j的遍历需要从大到小，否则会修改i-1次循环时存储的dp值。

dp[C]
size[N]#体积
value[N]#价值
for i=1 to n:
	for j=C to 1:
        if(j>=size[i])
        	dp[j]=max(dp[j],dp[j-size[i]]+value[i])
return dp[C]

第8章 贪心算法

8.12 给出一个具有最少顶点的图，证明此贪心算法求解s到t的距离不总是正确的。贪心算法：从s开始，到最近的顶点，称为x；从x出发，到最近的顶点，称为y，最终重复该做法到达t

graph LR
   s-->|1|x
   x-->|3|t;
   s-->|3|t;

如图所示，采用此贪心算法得到s->x->t的距离为4，而s到t的距离为3

8.14 DIJKSTRA算法是最优的吗？请解释

对于任意两点间距离均不为负的情况，是最优的。

DIJKSTRA算法基于贪心的思想，实现了全局最优。因为每次取出了未访问结点中距离最小的结点加入已访问结点中，再用该结点更新其他未访问结点的距离，此时被更新的未访问节点距离肯定是起点能通过已访问节点到达该节点的最短距离，如此一直更新距离直到访问完所有节点。

8.23 对图8.8中所示的无向图应用算法KRUSKAL找出最小耗费生成树，给出所得结果

已选取的节点集合$S$，已选取的边数量$cnt$，最小生成树权值和$ans$

1. 首先对边权从小到大排序

   边权-(端点，端点)

​ $Sorted-Edges:$[1-(1,2)、2-(1,4)、2-(2,4)、3-(3,6)、3-(5,6)、4-(3,5)、6-(1,3)、6-(4,6)、7-(2,3)、7-(4,5)、9-(3,4)]

2. 从小到大遍历排序后的边，决定是否选取该边

   如果该边的两个端点不在同一集合中就可选取，当$|S|=n$且$cnt=n-1$时退出遍历

​ 1：选取，$S=\{1,2\},cnt=1,ans=1$

​ 2：选取，$S=\{1,2,4\},cnt=2,ans=3$

​ 2：不选取

​ 3：选取，$S=\{1,2,3,4,6\},cnt=3,ans=6$

​ 3：选取，$S=\{1,2,3,4,5,6\},cnt=4,ans=9$

​ 4：不选取

​ 6：选取，$S=\{1,2,3,4,5,6\},cnt=5,ans=15$，此时退出循环

最小耗费为15，选取的边为1-2、1-4、1-3、3-6、5-6

8.26 设$e$是无向图$G$中一条有最小权重的边，证明$e$属于$G$的某个最小耗费生成树

用反证法：

设$e$的两个端点为$v_s,v_t$，则$v_s,v_t\in v(G)$

假设$e$不属于$G$的任何最小耗费生成树，对于$\forall MST \subseteq G$，有$v(MST)=v(G),|e(MST)|=|v(G)|-1$

则$v_s,v_t\in V(MST)$，假设$v_s,v_t$在$MST$中已存在路径$v_sv_{1}...v_kv_t$

现在我们将$MST$加入边$e$，显然存在环路$C=v_sv_1...v_kv_t+v_tv_s$，并且$w(v_tv_s)<w(v_sv_1...v_kv_t)$

因此我们可以删除原路径$v_sv_1...v_kv_t$得到耗费更小的$MST_1$，显然这与$MST$是$G$的最小耗费生成树冲突。

因此$e$属于$G$的某个最小耗费生成树

8.2 5.7节中描述的MAJORITY是贪心算法吗？请解释

MANORITY不是贪心算法，因为在candidate()函数中没有寻找局部最优解的迭代过程。

13.3 考虑13.2节中介绍的3着色算法，试解释如何在算法执行的整个过程中能有效的检验当前向量是否是部分的

假设当前向量为$(c_1,c_2,c_3,...c_m)$，且$c_1$到$c_m$均被着色，可以遍历每一个可能的组合判断其是否冲突

for i=1 to m-1:
    for j=i+1 to m:
        if( connect(i,j)==True and ci==cj)
        	return False
         endif
    endfor
endfor
return True

如果点$i$和点$j$互相邻接且$c_i$等于$c_j$，则不是部分向量

13.4 给出一个8皇后问题的递归算法

Queen[8][8]#存储当前的皇后位置的二维数组
ans=0#合法情况数量

solve8queen(row):
    if row>8
    	ans+=1
    	print_queen()
    	return
    for column=1 to 8:
        if NoConflict(row,column)==True:
            Queen[row][column]=1
            solve8queen(row+1)
            Queen[row][column]=0

#检测是否存在位置冲突
NoConflict(row,column):
    #检查列是否冲突
    for i=1 to 8:
        if Queen[i][column]==1:
        	return False
    #检查对角线是否冲突
    for i=1 to 8:
        j1=column-row+i
        if(j1<=8 and j1>=1 and Queen[i][j1]==1)
        	return False
        j2=column-i+row
        if(j2<=8 and j2>=1 and Queen[i][j2]==1)
        	return False
    return True
        
solve8queen(1)
return ans