算法设计与分析(四)

王多强 wdq0818@http://www.77cn.com.cn

1.基本概念1)顺序统计量：在一个有n个元素组成的集合中，第i小的元素称为该集合的第i个顺 序统计量 (order statistic) 。 如：在一组元素组成的集合中， 第1个顺序统计量(i=1)是该集合中的最小值； 第n个顺序统计量(i=n)是该集合中的最大值；

2)中位数：对一个有n个元素的集合，将数据排序 后(从大到小或从小到大),位置在最 中间的数称为该集合的中位数。

当元素数为奇数时，中位数出现在i=(n+1)/2处；如：1、2、3、6、7的中位数是3。

当元素数为偶数时，中位数取作第n/2个数据与第n/2+1个数据的算术平均值。如：1、2、3、5的中位数是2.5。

当元素数为偶数时，也可视为存在两个中位数，分别出现 在i=n/2(称为下中位数)和i=n/2+1(称为上中位数) 处。

如： 1、2、3、5的下中位数是2,上中位数是3。一般情况下，不管元素数是偶数或奇数， 下中位数： i (n 1) / 2 , 上中位数： i (n 1) / 2 注：一般取下中位数。 如：1)1、2、3、6、7的中位数是3。

(5 1) / 2 (5 1) / 2 32)1、2、3、5的下中位数是2,上中位数是3。

下中位数： (4 1) / 2 2上中位数： (4 1) / 2 3

中位数的性质： 中位数将数据分成两部分，一部分大于等于该数值，一部 分小于等于该数值。 中位数是一组数据的中间水平。 统计学意义：中位数≠平均数例：利用中位数衡量一下工资水平 。

1)排序

元素集合排序后，位于第i位的元素即为该集合 的第i个顺序统计量。时间复杂度：O(nlogn)

2)选择算法找元素集合里面的第k小元素，该元素为集合的 第k个顺序统计量。 时间复杂度：O(n) 3)求中位数：求中间元素。

3、实例例4.1:石油管的最优位置Olay教授正在为一家石油公司咨询，公司正在计划建 造一条由东向西的大型管道。该管道要穿过一个有n口井的 油田。从每口井中都有一条喷油管沿最短路径与主管道直接 相连(或南或北),如图所示

给定各口井的x坐标和y坐标。问，Olay教授如何选择主 管道的最优位置(即使得各喷管长度总和最小的位置)?

算法分析：1)由于主管道由东向西，因此要使相连油井与主管道的 喷油管最短，喷油管方向必须南北相连，与主管道垂直，即主

管道的最优位置应为一条y=yk的水平线。

即，问题的解是求最优位置yk。2)为了使yk与各油井的y座标y1,……,yn间的距离和最 短，我们将y1,…,yn由小到大排序，选择最中间的那个点作 为yk。

即，确定主管道最优位置，就是求n个油 井的y坐标的中位数。

主管道最优位置：若油井数为奇数，则第(n+1)/2

小的y坐标作为yk; 若油井数为偶数，则第n/2小的y坐标值与第(n/2+1)小 的y坐标值的平均数作为yk的值。

问题：证明：按照上述策略设计的主管道位置是最优的。 证明：该最优位置可在线性时间内确定。

对分别具有正的权重ω1, ω2,..., ωn且 i i 1 条件的元素xk: 和

n

1

的n个不同元素x1,x2,...,xn,带权中位数是满足如下

xi xk

i

1 2

xi xk

i

1 2

所有小于xk的元素

所有大于xk的元素 隐含有序

带权中位数应用：1)一维空间上的问题： 一条直线上有若干个带权的点p1,p2,...,pn,它们 的权重分别是ω1, ω2,..., ωn,在该直线上寻找一个点 p,使得n i 1 i i

d ( p, p ) 最小，其中d(a,b)表示点a与b

之间的距离d(a,b)=|a-b|

——称点p为该n个点的一维带权中位数。

分析：由于各点被赋了权，因此上述带权中位数p未必是按递增排序后的p1,p2,…,pn中处于中间位置的 那个点(甚至p不一定是p1,p2,...,pn 中的一个),而是 满足下述条件的一个点： 在递增序列p1,…,pk-1,pk,pk+1,…,pn中，子序列p1 ,…,pk-1的权和小于等于1/2,并且子序列pk+1,…pn的 权和也小于等于1/2(这里 i i 1xi xkn

1 ),即

i

1 2

和

xi xk

i

1 2

(试比较上述定义和前面的带权中位数的定义)

例4.2 一维邮局位置问题已知n个邮局分布在一条直线上，坐标点分别为 p1,p2, ...,pn,一邮递员每天需要多次到这些邮局取邮 件，设邮递员所处位置为点p。由于时间不一致，邮 递员每次到一个邮局取件后需要先回到p点，然后再 去下一个邮局。设邮递员每天到这些邮局的次数分别 ω1, ω2,..., ωn。 问，p设在哪里可使得邮递员每天到各个邮局走的 总里程最短？

分析：1)图示p1 p2 p pn

2)权重：邮递员每天需要到邮局的取件次数即为该问 题的权重，可换算成为[0..1]值。

3)里程：对邮局i,邮递员从p处出发到pi处，每天的里程数为ωid(p,pi),这里，d(p,pi)=|p-pi|, 代表p到pi的距离(注：这里只考虑单向); n 所以，该问题即是求 i d ( p, pi ) 的最小i 1

值——带权中位数问题。

2)二维空间上的问题： 二维平面上分布着n个点p1, p2,... pn,点pi的坐标 用(xi,yi)表示，每个点附有一个权重ωi, i 1。 n

定义点p1(x1,y1)与点p2(x2,y2)之间的距离是d(p1, p2)=|x1-x2|+|y1-y2|

i 1

(称为Manhattan距离),现在二维平面上找一个点p(x,y),使得 i d ( p, pi )最小，则称p为该二维平n i 1

面上n个点的带权中位数。(注：常用度量有欧几里德距离，曼哈顿距离和明考斯基距离 d(i,j) = (|xi1-xj1|q+|xi2-xj2|q+……+|xip-xjp|q)1/q)