算法概论(DPV)习题解答——第2章 分治算法

书籍介绍：

https://book.douban.com/subject/3155710/

配套课程：

CS170（伯克利），CS161（斯坦福）

github仓库：

https://github.com/Doraemonzzz/Algorithm-DPV

参考资料：

https://www.cnblogs.com/atyuwen/archive/2009/11/10/algorithmsexercisessolution.html

https://stackoverflow.com/questions/36316109/what-is-the-complexity-of-long-division

https://stackoverflow.com/questions/2884172/algorithm-for-dividing-very-large-numbers

https://zhuanlan.zhihu.com/p/62088196

https://stackoverflow.com/questions/10213929/linear-3sat-a-version-of-3sat-in-linear-time

这次回顾第2章，分治算法。

第2章

2.2

数列$\{b^{k}\}_{k=0}^{\infty}$将$[1,\infty)$划分为区间：

$$\{[b^{i},b^{i+1})\}_{i=0}^{\infty}$$

那么必然存在$i$，使得

$$\begin{aligned} b^{i} &\le n < b^{i+1}\\ b^{i+1}&\le nb < b^{i+2}\\ \end{aligned}$$

从而

$$b^{i+1}\in (n, nb] \subset [n,nb]$$

2.13

(b)

利用数学归纳法可证

$$B_{2k}= 0$$

对于$B_{2k+1}$，利用递归的性质可得：

$$B_{2k+1}=\sum_{i=0}^{k-1} B_{2i+1}B_{2(k-i) -1}$$

(c)

结论：

$$B_{n} \ge 2^{cn} , n=2k+1 , k\ge 2^c, c= 1/5$$

利用数学归纳法证明即可：

基本情形：

当$n=5$，即$k=2$时，

$$B_n = 2 \ge 2^{5c} =2$$

基本情形结论成立。

假设对于$n\le m -1$结论成立，那么对于$n = m$，我们有

$$\begin{aligned} B_{2k+1} &=\sum_{i=0}^{k-1} B_{2i+1}B_{2(k-i) -1}\\ &\ge \sum_{i=0}^{k-1} 2^{c\left(2i+1+ 2(k-i) -1 \right)}\\ &\ge k 2^{c(2k)} \\ &\ge 2^{c(2k +1)} \end{aligned}$$

所以$n=m$时结论亦成立。

2.16

如果$A$中每个数都是非负正整数，那么位置为$i$的数必然大于等于$i$，所以可以设置二分法的上界和下界为$0, x$；

否则将$A$中每个数和$x$都减去$A[0]$，那么可以转化为之前的情形。

备注：这里数组下标假设从$0$开始。

2.17

• 初始化$l=1, r= n$
• while $l<r$:
  • $m=\left[\frac{l+r} 2\right]$
  • 如果$A[m] = m$，返回$m$
  • 如果$A[m] < m$，令$ l= m - 1$
  • 否则，令$l=m +1$

正确性说明：

如果$A[m] < m$，那么对于$i\ge 0$，都有

$$A[m+i] < A[m] + i < m + i$$

$A[m]>m$时同理。

2.18

利用类似课本61页的方法。

二分搜索算法可以用决策树来描述，该决策树的每个节点形式为$A[i]\le z$，那么该决策树一共有$n$个叶节点，决策树对应的高度（对应操作次数）

$$\ge \log n$$

所以结论成立。

2.19

(a)

假设merge输入的两个数组长度分别为$n,m$，那么merge的时间复杂度为$\Theta(n + m)$，从而总时间复杂度为

$$\Theta \left(\sum_{i=1}^k in\right)=\Theta(k^2 n)$$

(b)

算法的输入为$k$个长度为$n$的有序数组，记为$[A_1,\ldots ,A_k]$，函数接口为

$$\text{mergekn}(k, n, [A_1,\ldots ,A_k])$$

对应的时间复杂度为$T(k, n)$。

现在构造如下算法：

• $l = \text{mergekn}([k/2], n, [A_1,\ldots ,A_{[k/2]}])$
• $r = \text{mergekn}(k-[k/2], n, [A_{[k/2] +1},\ldots ,A_{k}])$
• return $\text{merge}(l, r)$

时间复杂度递推关系

$$T(k, n) = 2T(k/2, n) + \Theta( kn)$$

所以总时间复杂度为

$$\Theta(kn\log k)$$

2.20

• 遍历数组，找到最大值和最小值$\max_i x_i , \min_i x_i$，记$M=\max_i x_i- \min_i x_i$，构造$M+1$个桶，第$k$个桶中记录值$\min_i x_i + k, k=0,\ldots, M$对应的索引。
• 再次遍历数组，将$i$放在第$x_i -\min_i x_i $个桶中。

时间复杂度：

第一步遍历$n$个元素，构造$M$个桶，时间复杂度为$\Theta(n+m)$；第二步遍历$n$个元素，时间复杂度为$\Theta(n)$。

所以总时间复杂度为$\Theta(n+m)$。

2.21

(a)

考虑一般的问题，$x\sim p(x)$，那么

$$\mu_{\text{median}} = \arg\min \mathbb E[|x-\mu|]$$

证明：

记

$$f(\mu)=\mathbb E[|x-\mu|]$$

化简可得

$$\begin{aligned} f(\mu)&=\mathbb E[|x-\mu|]\\ &= \int_{x< \mu } (\mu -x) p(x) dx +\int_{x\ge \mu } (x-\mu) p(x) dx\\ &= \mu \int_{x< \mu } p(x) dx-\mu\int_{x\ge \mu } p(x) dx - \int_{x< \mu } xp(x) dx + \int_{x\ge \mu } xp(x) dx \end{aligned}$$

求导得

$$\begin{aligned} f'(\mu) &= \int_{x< \mu } p(x) dx+\mu p(\mu) -\int_{x\ge \mu } p(x) dx + \mu p\mu -\mu p(\mu) - \mu p(\mu)\\ &= \int_{x< \mu } p(x) dx-\int_{x\ge \mu } p(x) dx\\ f''(\mu) &= 2p(\mu) \\ &\ge 0 \end{aligned}$$

令$f’(\mu) =0$可得

$$\begin{aligned} \int_{x< \mu } p(x) dx&= \int_{x\ge \mu } p(x) dx \\ \mu&= \mu_{\text{median}} \end{aligned}$$

从而$f(\mu)$在$\mu =\mu_{\text{median}} $处取极小值。

对于此特殊情形，构造特殊的概率分布：

$$p(x=x_i) =\frac 1 n , i=1,\ldots, n$$

此时

$$\mu_{\text{median}} = \mu_1$$

(b)

略。

(c)

记

$$\begin{aligned} x_{(1)}&= \min_i x_i\\ x_{(n)}&= \max_i x_i \end{aligned}$$

如果$\mu < x_{(1)}$，那么

$$\max _{i}\left|x_{i}-\mu\right| > |x_{(n)} - x_{(1)}|$$

如果$\mu > x_{(n)}$，那么

$$\max _{i}\left|x_{i}-\mu\right| > |x_{(n)} - x_{(1)}|$$

如果$x_{(1)} \le \mu \le x_{(n)}$，那么

$$\max _{i}\left|x_{i}-\mu\right| \ge \frac 12 |x_{(n)} - x_{(1)}|$$

当且仅当

$$\mu = \frac 1 2 \left(x_{(n)} + x_{(1)}\right)$$

时等号成立。

2.23

大部分内容见cs170 hw2，这里只讨论(b)。

(b)

感觉结论有问题，主要是$n$为奇数的情形。

反例：

对于元素数量为奇数的数组：

如果直接保留多出来的一个元素：

[2,2,3,3,3,3,2] -> [2,3,3,2]

如果删除多出来的一个元素：

[2,2,3,3,3] -> [2,3]

这两种情形此题的结论都不成立。

正确的方法应该是使用摩尔投票法。

2.24

• 算法名称：quickSort
• 输入：数组$A$，起始位置$l$，终止位置$r$

流程如下：

• $\text{pivot} = \text{Randomchoice}(A,l, r)$
• $i =\text{partition}(A,l, r, \text{pivot})$
• $\text{quickSort}(A,l,i-1)$
• $\text{quickSort}(A,i+1,r)$

(b)

如果$A$是有序的，每次选择的pivot为最小元素，那么时间复杂度为

$$\Theta\left(\sum_{i=1}^n i \right)=\Theta(n^2)$$

(c)

pivot为第$i$大元素的概率为$1/n$，对应的时间复杂度为

$$T(i -1) + T(n-i)$$

所以时间复杂度满足递推关系

$$\begin{aligned} T(n) &= kn+\frac{1}{n} \sum_{i=1}^{n}(T(i-1)+T(n-i))\\ nT(n)&=kn^2 + \sum_{i=1}^{n}(T(i-1)+T(n-i)) \end{aligned}$$

取$n=n+1$可得

$$(n+1)T(n+1)=k(n+1)^2 + \sum_{i=1}^{n}(T(i -1)+T(n+1-i))$$

两式相减可得

$$\begin{aligned} (n+1)T(n+1)-nT(n)&=k(2n+1) +2T(n)\\ (n+1)T(n+1) -(n+2)T(n) &=k(2n+1)\\ \frac{T(n+1)}{n+2}-\frac{T(n)}{n+1}&=\frac{k(2n+1)}{(n+1)(n+2)}\\ &\le \frac{2k}{n} \end{aligned}$$

递推可得

$$\begin{aligned} \frac{T(n)}{n +1} - \frac{T(1)}{2} &=2k\sum_{i=1}^{n-1} \frac{1}{i}\\ T(n)&= \frac{n+1}{2} T(1) + 2k(n+1)\left(\sum_{i=1}^{n-1} \frac{1}{i}\right)\\ T(n)&= \Theta(n\log n) \end{aligned}$$

这里利用了

$$\sum_{i=1}^n \frac 1 i =\Theta(\log n)$$

2.25

(a)

• function pwr2bin($n$)
  • if $n = 1$: return $1010_2$
  • else:
    • $z=\text{pwr2bin}(n/2)$
    • return fastmultiply($z,z$)

时间复杂度的递推关系：

$$T(n)=T\left(\frac n 2\right) + \Theta(n^{\alpha})$$

因为

$$\log_2 1 < \alpha= \log_2 3$$

所以时间复杂度为

$$\Theta(n^{\alpha})$$

(b)

• function dec2bin($x$)
  • if $n=1$: return binary[$x$]
  • else:
    • split $x$ into two decimal numbers $x_L,x_R$ with $n/2$ digits each
    • return $\text{fastmultiply}(\text{pwr2bin}({n/2}), \text{dec2bin}(x_L)) + \text{dec2bin}(x_R)$

说明：

利用如下恒等式

$$x= x_L \times 10^{n/2} + x_R$$

注意到$n$位$10$进制数的范围是

$$[0, 10^{n}-1]$$

利用$l$位$2$进制数表示该范围，那么

$$\begin{aligned} 10^{n} -1&\le 2^{l} -1 < 10^{n+1} -1\\ n\log_2 10 &\le l < (n+1)\log_2 10\\ l &\in \Theta(n) \end{aligned}$$

所以函数的中间结果长度均为$\Theta(n)$，每一步的时间复杂度如下

$$\begin{aligned} \text{dec2bin}(x_L)&: T\left( \frac n 2\right)\\ \text{dec2bin}(x_R)&: T\left( \frac n 2\right)\\ \text{pwr2bin}\left( \frac n 2\right)&:\Theta(n^{\alpha}) \\ \text{fastmultiply}(\text{pwr2bin}({n/2}), \text{dec2bin}(x_L))&: \Theta(n^{\alpha}) \end{aligned}$$

所以时间复杂度的递推关系为

$$T(n) =2 T\left( \frac n 2\right) +\Theta(n^{\alpha})$$

因为

$$\log_2 2 =1< \alpha =\log_2 3$$

所以

$$T(n)\in \Theta(n^{\alpha })$$

2.26

错误，利用如下事实即可

$$\begin{aligned} xy &= \frac{(x+y)^2 -(x- y)^2}{4}\\ &=[(x+y)^2-(x- y)^2] >> 2 \end{aligned}$$

右移操作的时间复杂度为$\Theta(n)$，所以两数相乘的渐进时间复杂度不高于平方运算的渐进时间复杂度；而平方运算是一种特殊的两数相乘，所以其渐进时间复杂度小于等于两数相乘的渐进时间复杂度，从而两数相乘的渐进时间复杂度和平方运算的渐进时间复杂度相同。

2.29

(a)

$i$	$z$
无	$a_n$
$n-1$	$a_{n-1}+a_nx$
$n-2$	$a_{n-2}+a_{n-1}x+a_nx^2$
$\ldots$	$\ldots$
$i$	$\sum_{j=i}^n a_{j} x^{j-i} $
$\ldots$	$\ldots$
$0$	$\sum_{j=0}^n a_{j} x^{j} $

(b)

每轮的加法和乘法次数都为$1$，所以一共有$n$次乘法和$n$次加法。

不存在更优的算法，原因如下：

• $n+1$项相加至少要$n$次加法
• $a_i \times x^i,i=1,\ldots,n$至少需要$n$次乘法（常数和$x^i$相乘）

2.31

假设

$$\begin{aligned} a &= \prod_{i=1}^kp_i ^{n_i}\\ b &= \prod_{i=1}^k p_i ^{m_i} \end{aligned}$$

其中

$$p_1\le p_2\le\ldots \le p_k\\ n_i \ge 0, m_i \ge 0, p_i为质数,i=1,\ldots, k$$

那么

$$\gcd (a, b) = \prod_{i=1}^kp_i ^{\min (m_i, n_i)}$$

(a)

如果$a, b$都是偶数，那么

$$\begin{aligned} p_1&= 2\\ n_1&\ge 1\\ m_1&\ge 1 \end{aligned}$$

因此

$$\begin{aligned} \gcd (a, b) &= \prod_{i=1}^kp_i ^{\min (m_i, n_i)}\\ &= p_1 ^{\min (m_1, n_1) }\prod_{i=2}^kp_i ^{\min (m_i, n_i)}\\ &=2\times p_1 ^{\min (m_1, n_1) -1}\prod_{i=2}^kp_i ^{\min (m_i, n_i)}\\ &=2 \times \gcd (a/ 2, b/2) \end{aligned}$$

如果$a,b$其中一个是偶数，另一个是奇数。不妨设$a$是奇数，$b$是偶数，那么

$$\begin{aligned} p_1&= 2\\ n_1&=0\\ m_1&\ge 1 \end{aligned}$$

那么

$$\begin{aligned} \gcd (a, b) &= \prod_{i=1}^kp_i ^{\min (m_i, n_i)}\\ &= p_1 ^{\min (m_1, n_1) }\prod_{i=2}^kp_i ^{\min (m_i, n_i)}\\ &=\prod_{i=2}^kp_i ^{\min (m_i, n_i)}\\ &=\gcd (a, b/2) \end{aligned}$$

如果$a,b$都是奇数，那么

$$\begin{aligned} \gcd (a, b) &= \gcd (a-b, b)(a-b为偶数, b为奇数,运用之前的结论)\\ &= \gcd ((a-b) /2, b) \end{aligned}$$

(b)

利用递推式即可：

$$\operatorname{gcd}(a, b)=\left\{\begin{array}{ll} 2 \operatorname{gcd}(a / 2, b / 2) & \text { 如果 } a, b \text { 都是偶数 } \\ \operatorname{gcd}(a, b / 2) & \text { 如果 } a \text { 是奇数, } b \text { 是偶数 } \\ \operatorname{gcd}(a/2, b ) & \text { 如果 } a \text { 是偶数, } b \text { 是奇数 } \\ \operatorname{gcd}((a-b) / 2) & \text { 如果 } a, b \text { 都是奇数 } \end{array}\right.$$

(c)

当前算法：

假设输入为$a,b$，对应长度为$n,m$，对应的时间复杂度为$T(n,m)$，那么时间复杂度满足递推关系：

$$T(n, m)=\begin{cases} T(n-1,m-1)+ \Theta(n+m) & a, b都为偶数\\ T(n,m-1)+ \Theta(m) & a为奇数, b都为偶数\\ T(n-1,m)+ \Theta(n) & a, b都为奇数\\ T(\max(n,m)-1,m)+ \Theta(n+m ) & a为偶数, b都为奇数\\ \end{cases}$$

所以每一步会使得输入的某个元素的位数减$1$，所以最多经过$n+m$步，算法会停止，每一步的时间复杂度为$\Theta(n+m)$，所以总时间复杂度为

$$\begin{aligned} \Theta\left(\sum_{i=1}^{n+m} i \right) &=\Theta\left(\frac{(n+m)(n+m+1)}{2} \right)\\ &=\Theta\left(n^2 + m^2 + nm\right)\\ \end{aligned}$$

特别的，对于此问题，$n=m$，所以时间复杂度为

$$\Theta(n^2)$$

欧几里得算法：

首先证明Lame定理（参考sicp第32页）：

• 如果欧几里得算法需要$k$步计算出一对整数的$\gcd$，那么这对数中最小的数必然大于等于第$k$个斐波那契数。

证明：

考虑算法中连续三组参数$(a_{k+1},b_{k+1}) \to (a_k, b_k)\to (a_{k-1}, b_{k-1})$

下面证明

$$b_{k+1}\ge b_{k} + b_{k-1}$$

由定义可得

$$\begin{aligned} a_{k}&= b_{k+1}\\ a_{k-1}&= b_k\\ b_{k-1}&= a_k \mod b_{k}\\ a_{k}&= q b_k + b_{k-1} \end{aligned}$$

对最后一式做变量替换可得

$$b_{k+1}= q b_k +b_{k-1}\ge b_k + b_{k-1}$$

又因为

$$\begin{aligned} b_0 &= 0\ge \text{Fib}(0)\\ b_1 &\ge 1 = \text{Fib}(1) \end{aligned}$$

所以利用数学归纳法，我们可得

$$\begin{aligned} b_{k+1}&\ge b_k + b_{k-1}\\ &\ge \text{Fib}(k)+\text{Fib}(k-1)\\ &= \text{Fib}(k) \end{aligned}$$

结论得证。

利用该结论，我们可得对于两个长度为$n$位的输入，$\gcd$运算的次数为$O(n)$，每次运算的时间复杂度由下式子确定：

$$\begin{aligned} q&= a_k / b_k\\ b_{k-1}&= a_{k}- q b_k \end{aligned}$$

除法的时间复杂度为$O(n^2)$（基本算法），所以总的时间复杂度为

$$O(n^3)$$

说明该算法优于欧几里得除法。

大整数除法时间复杂度参考资料：

https://stackoverflow.com/questions/36316109/what-is-the-complexity-of-long-division

https://stackoverflow.com/questions/2884172/algorithm-for-dividing-very-large-numbers

https://zhuanlan.zhihu.com/p/62088196

2.33

(a)

利用反证法。

由$M$非零可得存在元素$M_{pq}\ne 0$，下面将$2^n$个可能的取值进行分组，$v^{1},v^{2}$属于一组，当且仅当

$$\begin{aligned} v^{1}_i&=1-v^{2}_i,i=q\\ v^1 _i&= v^2_i,i\neq q \end{aligned}$$

不难看出一共划分为$2^{n-1}$组。

如果结论不成立，那么必然存在同组的两个$v^1,v^2$，同时满足

$$\begin{aligned} Mv^{m}&= 0\\ \sum_{t=1}^n M_{pt}v^m_t&= 0(考虑第p行)\\ M_{pq}v^m_q &=-\sum_{t\neq q} M_{pt}v^m_t\\ m&=1,2 \end{aligned}$$

注意到

$$v^1 _i= v^2_i,i\neq q$$

所以我们有

$$\begin{aligned} M_{pq}v^1_q &=-\sum_{t\neq q} M_{pt}v^1_t\\ &= -\sum_{t\neq q} M_{pt}v^2_t\\ &= -M_{pq}v^2_q \end{aligned}$$

利用$M_{pq}\ne 0$，我们可得

$$v_q^1 + v_q^2 =0$$

这就与

$$v^{1}_q=1-v^{2}_q$$

矛盾。

(b)

注意到

$$ABv= Cv \Leftrightarrow (AB-C)v= 0$$

所以

$$\text { 如果 } A B \neq C, \quad \text { 则 } \operatorname{Pr}[A B v=C v] \le 1 / 2$$

注意到$ABv=A(Bv)$，所以计算$ABv,Cv$的时间复杂度为$O(n^2)$。

现在设置参数$k$，构造如下算法：

• flag = true
• for $i=1,\ldots,k$,
  • 随机初始化$v$
  • 如果$AB v \neq Cv$
    • flag = false
    • break
• return flag

算法说明：

如果$AB\neq C$，那么flag = true的概率$\le 1/ 2^k$，取稍大的$k$，那么可以认为该事件几乎不可能发生，所以可以近似认为flag = true时，$AB=C$；flag = false时，$AB\neq C$。

2.34

思路：

动态规划，对下标为$i$的变量，维护变量$\{\max(i-10, 1),\ldots, \min(i+10, n)\}$的取值即可。

• 初始化可行集$S =\{\varnothing \}$（该集合为可行集的集合）
• 布尔公式$B$
• for $i=1,\ldots, \min(21, n)$:
  • $B_1= B$
  • $S_1=\{\}$
  • for $s\in S$:
    • $B_1=B(s)$
    • for $v=\text{false}, \text{true}$:
      • $B_1=B_1((i, v))$
      • if $B_1$不可满足：
        • break
      • $s= s\cup \{(i, v)\}$
      • $S_1= S_1\cup s$
  • $S=S_1$
• for $i=2,\ldots, n$:
  • $B_1= B$
  • $S_1=\{\}$
  • $j=\min(i+10, n)$
  • for $s\in S$:
    • $B_1=B(s)$
    • for $v=\text{false}, \text{true}$:
      • 如果$j$的子句不都可满足：
        • break
      • $s= s\cup \{(j, v)\}-\{(\max(i-10, 1), v’)\}$
      • $S_1= S_1\cup s$
  • $S=S_1$
• return $S$中任意元素

时间复杂度：

$n$轮循环，集合$S$的元素数量$\le 2^{21}$，所以是线性时间复杂度。

参考资料：

https://stackoverflow.com/questions/10213929/linear-3sat-a-version-of-3sat-in-linear-time