算法导论 9 Problems 答案

9-1

a

先直接进行排序,需要 O(nlgn) 的运行时间,然后直接返回最后 i 个数。这个算法的总体时间复杂度为 O(nlgn)

b

使用算法 BUILD-MAX-HEAP 对整个数组进行建堆,需要 O(n) 的运行时间。然后使用 i 次算法 EXTRACT-MAX 分别弹出当前最大值,每次使用的运行时间为 O(lgn)。这个算法的总体时间复杂度为 O(n+ilgn)

c

先用算法 SELECT 求出第 ni+1 小的数(也就是第 i 大的数),需要 O(n) 的运行时间。然后直接对后面 i 个元素进行排序后直接返回,这个过程需要 O(ilgi) 的运行时间。这个算法的总体时间复杂度为 O(n+ilgi)

9-2

a

如果第 3 行代码返回的 q 恰好是下标最大值 r,那么 k=rp+1,由于 irp+1 是恒成立的,因此必定进入第 6 行的分支。此时的递归调用相当于是 SIMPLER-RANDOMIZED-SELECT(A, p, r, i),这没有对区间做任何的缩减。因此,在最坏情况下相当于进行无限递归,程序不会终止。

b

算法 SIMPLER-RANDOMIZED-SELECT 的第 3 行相当于从区间 A[p:r] 中均匀随机选择一个数作为支点,最终划分完成后(假设这是第 i 小的数),在第 6-7 行中选择一个分支继续进行查找。

假设在最坏情况下,每次递归查找的都是大小比较大的那个区间,那么假设 T(n) 为运行时间,有

T(n)1ni=1nT(max{i,ni})+O(n)

整理一下,可以写成

T(n)1n1i=1n1T(max{i,ni})+O(n)

考虑消去 max。如果 n1 是奇数,那么项 T(n/2) 会出现 1 次,项 T(n/2+1),T(n/2+2),,T(n1) 都会出现 2 次;如果 n1 是偶数,那么项 T((n+1)/2),T((n+1)/2+1),,T(n1) 都会出现 2 次。

因此为了避免分别讨论,缩放时,n1 为奇数的情况再添加多一个项,那么可以写出

T(n)2n1i=n/2n1T(i)+O(n)

假设 T(n)cn,那么有

T(n)2n1i=n/2n1T(i)+O(n)2cn1(n/2+n1)(nn/2)2+O(n)=c(n/2+n1)(nn/2)n1+O(n)c(n/2+1+n1)(nn/21)n1+O(n)=3cn(n2)4(n1)+O(n)3cn(n2)4(n2)+O(n)=34cn+O(n)cn(A)

其中步骤 (A) 使用了如下假设:c 足够大,使得 cn4 的渐进增长快于 O(n)

因此有 T(n)=O(n)

9-3

这里的中位数默认是第 n2 小的数。

需要注意的是,通过哈希表,我们可以把相同的 x 合并成一个,并且其权值进行相加。只要哈希表的性能足够优秀,那么这个预处理需要 Θ(n) 的时间复杂度完成。因此在接下来的过程中,我们默认 x 是两两不同的。

a

小于中位数的数有 n21 个。那么这些数的权值之和为 1n(n21)。可以发现,当 n 为偶数时,权值和为 121n,当 n 为奇数时,权值和为 n12n。无论那种情况都小于 12

大于中位数的数有 nn2=n2 个。那么这些数的权值之和为 1nn2。无论 n 取何值,权值之和总小于等于 12

因此,{x} 的普通中位数就是这种特殊情况下的带权中位数。

b

算法 GET-WEIGHTED-MEDIAN1 给出了求取一个带权中位数的算法。其中排序算法的时间复杂度假设为 O(nlgn)

1
2
3
4
5
6
7
8
9
// 数组A中的每一个元素都有两个属性,分别为x和w,x表示数值,w表示权重。
GET-WEIGHTED-MEDIAN1(A, n)
sort A[1 : n] by key x
s = 0
for i = 1 to n
s = s + A[i].w
if s >= 0.5
return A[i].x
return NIL

直接排完序后,从小到大将所有数的权值逐渐相加,将第一个大于等于 0.5 的数直接返回。如果输入是合法的(权值之和为 1),那么第 7 行的代码 return NIL 不会被运行到。

c

整个算法通过如下伪代码给出给出。子程序 RANDOMIZED-PARTITION-WEIGHTEDPARTITION-WEIGHTED 与原版的行为基本相同,多统计了一个权值之和。它们的时间复杂度为 Θ(n)

算法 MEDIAN-WEIGHT 的时间复杂度 T(n) 的分析过程和 9-2-b 完全一致,为 T(n)=O(n)。第 5 行代码第一次对整个数组进行了一次划分,因此有 T(n)=Ω(n)。那么整个算法的时间复杂度为 T(n)=Θ(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// PARTITION-WEIGHTED返回两个值,一个是划分后这个数的下标q,一个是A[p : q]中所有数的权值之和。
PARTITION-WEIGHTED(A, p, r)
s = 0
x = A[r].x // the pivot
i = p – 1 // highest index into the low side
for j = p to r – 1 // process each element other than the pivot
if A[j].x < x // does this element belong on the low side?
i = i + 1 // index of a new slot in the low side
exchange A[i] with A[j] // put this element there
exchange A[i + 1] with A[r] // pivot goes just to the right of the low side
return i + 1, s + A[i + 1].w

RANDOMIZED-PARTITION-WEIGHTED(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION-WEIGHTED(A, p, r)

// 目标是求出最小的数x,使得小于等于x的所有权值之和大于等于0.5.
MEDIAN-WEIGHT(A, n)
pw = 0.5
p = 1
r = n
while p < r
q, nw = RANDOMIZED-PARTITION(A, p, r)
if nw >= pw
r = q
else
pw = pw - nw
p = q + 1
return A[p].x

d

假设 x 是目前的最小值解,且 x 不是带权中位数,即不满足带权中位数条件 xi<xkwi<12,xi>xkwi12 中的一个。

不失一般性,假设不满足第 2 个条件,那么有 pi>xwipi<xwi>0

k=mini=1n{|xpi|},那么取 l 使得 l[0,k)。从 x 向右迈出一小步 l,那么此时有

i=1nwid(x+l,pi)=pi<xwi(x+lpi)+pi>xwi(pixl)=pi<xwi(xpi)+pi>xwi(pix)l(pi>xwipi<xwi)=i=1nwid(x,pi)l(pi>xwipi<xwi)i=1nwid(x,pi)

由此可见,得到了一个更优秀的解 x+l

当不满足第 1 个条件时,则是按反方向走,证明方法类似。

因此,当 x 是带权中位数时,得到的解是最优的。

e

由于 i=1nd(p,pi)=i=1nwi(|xxi|+|yyi|)=(i=1nwi|xxi|)+(i=1nwi|yyi|),可以分别将两个维度的坐标看成是两个独立的一维问题进行解决。分别求出 x 坐标和 y 坐标后进行组合即可。

9-4

a

这个算法由 SELECT' 给出。基本思想是先一对对元素进行比较并且绑定,完成 n2 次比较后,递归划分出 n2 个小元素中前 i 小的元素。划分好后,第 i 小数必定是这 i 对数中的第 i 小数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SELECT'(A, n, i)
if 2 * i >= n
return SELECT(A, 1, n, i)
if n % 2 == 1
INSERT(A, +∞)
n += 1
m = n / 2
for i = 1 to m
if A[i] > A[i + m]
exchange A[i] with A[i + m]
combine A[i] and A[i + m]
SELECT'(A[1 : m], m, i)
let B[1 : i + i] be new array
for j = 1 to i
B[j] = A[i]
B[j + i] = the number that A[i] combine
return SELECT(B, 1, i + i, i)

b

我们使用代入法来证明 Ui(n)n=O(T(2i)lg(n/i))。假设 Ui(n)ncT(2i)lg(n/i)。那么有

Ui(n)n=(Ui(n/2)n/2)+T(2i)cT(2i)lg(n/2/i)+T(2i)cT(2i)(lg(n/2/i)+1)(A)cT(2i)(lg(n/i))

其中,步骤 (A) 假设了 c>1,并且足够大到消去符号

因此,Ui(n)n=O(T(2i)lg(n/i)),即 Ui(n)=n+O(T(2i)lg(n/i))

c

根据题目 9-4-b 的结论,可以得出:c,n0>0,n>n0,0Ui(n)ncS(2i)lg(n/i) 恒成立。

那么有

Ui(n)ncS(2i)lg(n/i)=cS(2i)(lgnlgi)cS(2i)lgn

构造一个新常数 c=cS(2i),那么这对常数 {c,n0} 说明 Ui(n)n=O(lgn),即 Ui(n)=n+O(lgn)

d

k2 时,i=n/k<n/2。因此根据题目 9-4-b 的结论,代入 i=n/k,可以得到 Ui(n)=n+O(S(2n/k)lgk)

9-5

a

和分析 RANDOMIZED-QUICKSORT 时的思想一致,如果我们选择的支点处在 min{zi,zj} max{zi,zk} 之间时,才会有讨论的意义。否则,每次划分区间时,这 3 个元素仍然处在同一个区间内部,zj zk 是否被比较仍然未知。并且按照上面的思想,zj zk 是否被比较,当且仅当 zj,zk 处在同一区间内,并且着两个数之一成为支点 q。那么分别考虑三种情况:

  1. zi<zj<zk 时,如果支点 q{zj,zk},那么就会产生对 zj,zk 的比较。如果 q[zi,zj),那么下一层递归将会进入区间 [zi,q),zj,zk 永远不会被比较。如果 q(zj,zk),那么 zj zk 将会被分隔开,永远不会被比较。此时 E[Xijk]=2ki+1

  2. zj<zk<zi 时,此时和情况 1 类似。此时 E[Xijk]=2ij+1

  3. zjzizk 时,类似的,如果 q(zj,zk),那么 zj zk 将会被分隔开,永远不会被比较;否则必定会被比较,此时 E[Xijk]=2kj+1

因此有:

E[Xijk]={2ki+1ifzi<zj<zk2ij+1ifzj<zk<zi2kj+1ifzjzizk

b

根据示性随机变量 Xi 的定义,有 Xi=j=1n1k=j+1nXijk。那么有

E[Xi]=E[j=1n1k=j+1nXijk]=j=1n1k=j+1nE[Xijk]=j=i+1n1k=j+1nE[Xijk]+j=1i2k=j+1i1E[Xijk]+j=1ik=inE[Xijk]=j=i+1n1k=j+1n2ki+1+j=1i2k=j+1i12ij+1+j=1ik=in2kj+1=2(j=i+1n1k=j+1n1ki+1+j=1i2k=j+1i11ij+1+j=1ik=in1kj+1)=2(k=i+2nki1ki+1+j=1i2ij1ij+1+j=1ik=in1kj+1)2(k=i+1nki1ki+1+j=1i2ij1ij+1+j=1ik=in1kj+1)

c

由题目 9-5-b 的推导继续进行。

E[Xi]2(k=i+1nki1ki+1+j=1i2ij1ij+1+j=1ik=in1kj+1)2(k=i+1n1+j=1i21+j=1ik=in1kj+1)=2(n2+j=1ik=in1kj+1)=2(n2+c=1n1c1ji,ij+c1n1)2(n2+c=1n1cc)2(n2+n)4n

d

算法 RANDOMIZED-SELECT 的整个过程是围绕子程序 RANDOMIZED-PARTITION 进行的,比较过程就在这个子程序中进行。

根据题目 9-5-c 的结论,所有调用子程序 RANDOMIZED-PARTITION 的过程中,总期望比较次数不超过 4n。因此算法 RANDOMIZED-SELECT 的时间复杂度为 O(n)

9-6

假设单个组的大小为 2k+1,其中 k 是一个正整数,且是常数。

a

此时意味着有前提条件:k2.

前 11 行代码,无非就是将所有为 5 的常量转化成 2k+1。这一段的代码运行时间仍然为 Θ(n)

第 12-13 行代码对每组 2k+1 个元素进行原地排序。由于每组内部元素数量相同,一共有 Θ(n) 组,这一段的运行时间仍然为 Θ(n)

第 16 行对中间的一组再进行一次调用,产生了 T(n/(2k+1)) 的开销。

第 17 行对数组进行了一次划分,这一段的运行时间仍然为 Θ(n)

总而言之,上面这部分算法内部开销的时间复杂度为 Θ(n)

第 20-24 行递归进入所划分的区间。按照这种划分方法,可以知道,第 16 行中的 x 至少有 n(k+1)2(2k+1)=k+14k+2n 个数比它大,至少有 k+14k+2n 个数比它小。因此每次进行下一次递归时,至多可以去除 k+14k+2n 个数。假设 T(n) 为对 n 个元素进行选择的运行时间,那么有

T(n)T(n/(2k+1))+T((3k+1)n/(4k+2))+Θ(n)

使用代入法,假设 T(n)cn,那么有

T(n)T(n/(2k+1))+T((3k+1)n/(4k+2))+Θ(n)c2k+1n+c(3k+1)4k+2n+Θ(n)=cnc(k1)4k+2n+Θ(n)cn(A)

其中,步骤 (A) 假设了 c 足够大,以至于项 c(k1)4k+2n 的渐进增长速度超过 Θ(n)。并且,由于 k2,因此这个项是恒正的。

因此有 T(n)=O(n)

由于第 17 行对数组进行了一次 Θ(n) 的划分,因此说明 T(n)=Ω(n)

因此最终有 T(n)=Θ(n)

b

此时意味着有前提条件:k=1.

那么 T(n) 可以写成

T(n)T(n/3)+T(2n/3)+Θ(n)

由于 k=1,项 c(k1)4k+2n 的值恒为 0,因此题目 9-6-a 的结论不适用。

那么假设 T(n)cnlgn,有

T(n)T(n/3)+T(2n/3)+Θ(n)cn3lgcn3+2n3lg2n3+Θ(n)=cnlgnc3lg274n+Θ(n)cnlgn(A)

其中,步骤 (A) 假设了 c 足够大,以至于 c3lg274n 的渐进增长速度超过 Θ(n)

因此有 T(n)=O(nlgn)

c

前 11 行代码是为了调整整个数组的长度是 9 的倍数。

第 12-13 行代码则是对组内的所有元素进行排序,每组有 3 个元素。排完序后的示意图如下:

第 16-17 行代码则是对大组中的所有中位数再次进行排序,由于排序元素数量恒定为 3 个。排完序后的示意图如下:

其中,蓝色区域表示比 x 小的数,黄色区域表示比 x 大的数。

因此可以发现,整个序列可以划分成大小为 9 的组,也就是说一共有 n9 组。其中一半的大组至少有 4 个数比 x 小,一半的大组至少有 4 个数比 x 大。那么在每一次的划分过程中,我们可以排除掉至少 n429=29n 个数。

由此继续进行划分下去,最终可以成功找到一个第 i 大的数。

d

第 1 行的 while 循环次数最多为 8,内部嵌套的 for 循环长度为 Θ(n),因此前 11 行代码的运行时间为 Θ(n)

第 12-13 行代码则是对组内的所有元素进行排序,由于排序元素数量恒定为 3 个,组数为 Θ(n)。因此第 12-13 行代码的运行时间为 Θ(n)

第 16-17 行代码则是对大组中的所有中位数再次进行排序,由于排序元素数量恒定为 3 个,大组的组数也是 Θ(n)。因此第 12-13 行代码的运行时间为 Θ(n)

第 20 行对中间的一个大组再进行一次调用,产生了 T(n/9) 的开销。

第 21 行对数组进行了一次划分,这一段的运行时间仍然为 Θ(n)

第 23-28 行递归进入所划分的区间。按照题目 9-6-c 的描述,这个开销最大为 T(7n/9)

那么可以写出 T(n) 的递推关系式:

T(n)T(n/9)+T(7n/9)+Θ(n)

进一步化简,有

T(n)T(n/9)+T(7n/9)+Θ(n)cn/9+7cn/9+Θ(n)=cncn/9+Θ(n)cn(A)

其中,步骤 (A) 假设了 c 足够大,以至于项 cn/9 的渐进增长速度超过 Θ(n)

因此有 T(n)=O(n)