书籍介绍:

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)$划分为区间:

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

从而

2.13

(b)

利用数学归纳法可证

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

(c)

结论:

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

基本情形:

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

基本情形结论成立。

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

所以$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]>m$时同理。

2.18

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

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

所以结论成立。

2.19

(a)

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

(b)

算法的输入为$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)$

时间复杂度递推关系

所以总时间复杂度为

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)$,那么

证明:

化简可得

求导得

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

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

对于此特殊情形,构造特殊的概率分布:

此时

(b)

略。

(c)

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

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

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

当且仅当

时等号成立。

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为最小元素,那么时间复杂度为

(c)

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

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

取$n=n+1$可得

两式相减可得

递推可得

这里利用了

2.25

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

时间复杂度的递推关系:

因为

所以时间复杂度为

(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)$

说明:

利用如下恒等式

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

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

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

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

因为

所以

2.26

错误,利用如下事实即可

右移操作的时间复杂度为$\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

假设

其中

那么

(a)

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

因此

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

那么

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

(b)

利用递推式即可:

(c)

当前算法:

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

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

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

欧几里得算法:

首先证明Lame定理(参考sicp第32页):

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

证明:

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

下面证明

由定义可得

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

又因为

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

结论得证。

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

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

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

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

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}$属于一组,当且仅当

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

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

注意到

所以我们有

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

这就与

矛盾。

(b)

注意到

所以

注意到$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