算法导论思考题9-2

算法导论中位数

字数统计: 2.1k阅读时长: 9 min

 2019/08/02   Share

9-2 (带权中位数)对分别具体以正权重$w_1,w_2,\dotsb,w_n$,且满足$\sum_{i=1}^{n}{w_i=1}$的$n$个互异的元素$x_1,x_2,\dotsb,x_n$来说，带权中位数$x_k$(较小中位数)是满足如下条件的元素：

$\sum_{x_i < x_k}w_i <\frac{1}{2} \quad和\quad\sum_{x_i > x_k}w_i \leq \frac{1}{2}$

例如，如果元素是$0.1 ,0.35 ,0.05 ,0.1 ,0.15 ,0.05 ,0.2$，并且每个元素的权重等于本身(即对所有$i=1,2,\dotsb,7都有w_i=x_i$)，那么中位数是0.1，而带全中位数是0.2。

a. 证明：如果对所有$i=1,2,\dotsb,n$都有$w_i=1/n$，那么$x_1,x_2,\dotsb,x_n$的中位数就是$x_i$的带权中位数。

证明：$x_i,x_2,\dotsb,n$的中位数（题目给的是低中位数）是$x_k=x$那么就有：

$\begin{aligned} |\{x_i| 1 \leq i \leq n,x_i < x\}| &< n/2 \\ |\{x_i| 1 \leq i \leq n,x_i > x\}| &\leq n/2 \end{aligned}$

这里解释下:

第1个式子是小于中位数的个数，因为是低中位数，无论集合是奇数偶数个都是小于$n/2$；

第2个式子是大于中位数的个数，当集合个数是奇数是，也是小于$n/2$，当集合个数为偶数时，等号成立。

同时因为每一个元素的权值都是置为$1/n$，那么就有：

$\begin{aligned} \sum_{x_i<x}{w_i} &= \sum_{x_i<x}{\frac{1}{n}} \\ &= \frac{1}{n}·\sum_{x_i<x}1 \\ &= \frac{1}{n}·|\{x_i| 1 \leq i \leq n,x_i <x\}| \\ &< \frac{1}{n} · \frac{n}{2} \\ &= \frac{1}{2} \end{aligned}$

满足带权中位数的第一个条件。同理，我们有：

$\begin{aligned} \sum_{x_i>x}{w_i} &= \sum_{x_i>x}{\frac{1}{n}} \\ &= \frac{1}{n}·\sum_{x_i>x}1 \\ &= \frac{1}{n}·|\{x_i| 1 \leq i \leq n,x_i > x\}| \\ &\leq \frac{1}{n}·\frac{n}{2} \\ &=\frac{1}{2} \end{aligned}$

第二个条件得证。因此当集合X的每个元素的权重都是$1/n$时，$x_1,x_2,\dotsb,x_n$的中位数$x_k=x$，同时也是带权中位数。

b. 利用排序，设计一个最坏情况下$O(nlgn)$时间的算法，可以得到$n$个元素的带权中位数。

Step1、可以对元素$x_1,x_2,\dotsb,x_n$采用归并排序或者堆排序算法来升序排序。

Step2、然后从最小$x_1$开始，从左往右遍历每一个，将权值累加起来，当权值超过$1/2$，那么最后一个导致超过$1/2$的元素就是带权中位数。

Step1时间复杂度为$O(nlgn)$，Step2时间复杂度为$O(n)$。满足题目要求。

c. 说明如何利用像9.3节的SELECT这样的线性时间中位数算法，在$\Theta(n)$最坏情况时间内求出带权中位数。

线性时间查找带权中位数的思想是二分查找。算法工作流程如下:

1、问题规模$n \leq 2$，可以在$O(1)$情况下暴力解决。

2、问题规模$n > 2$时，我们先找到集合$X$的中位数$x_k =x$，将集合$X$用$x_k$划分为两个集合，下面称为$L=\{x_i|1 \leq i \leq n,x_i < x\}$和$G=\{x_i|1 \leq i \leq n,x_i >x\}$,然后计算$W_L$和$W_G$（两部分的权重）。根据$W_G$和$W_G$的权重情况，可以分为3种情况处理：

$\begin{cases} a、 x_k即为带权中位数 & W_L < 1/2 \ and \ W_G <1/2 \\ b、在集合L中查找 & W_L>1/2 \\ c、在集合G中查找 & W_G>1/2 \end{cases}$

在处理b、c情况时，我们为了避免下一次划分时重复计算$W_L$和$W_G$，对于情况b：我们可以将$w_k=w_k+W_G$，然后将$x_k$加入下一步要进行查找的集合$L$中。

下面时该算法的伪代码：

WEIGHTED-MEDIUM(X)
    //规模小于等于2，O(1)解决
    if X.size = 1
        return x[1]
    elseif x.size = 2
        if w[1]>=w[2]
            return x1
        else
            return x2
    //规模 >2，取中位数，二分递归进行
    else
        find the Medium x[k] in X[1,..,n]
        partition the set X by x[k] into L,G
        computer WL=sum of w[i] in the set L
                 WG=sum of w[i] in the set G
        if WL<1/2 and WG < 1/2
            return x[k]
        elseif WL > 1/2
            w[k]=w[k]+WG
            X'<--{x[i] in X | x[i] <= x[k]}
            return WEIGHT-MEDIUM(X')
        else
            w[k]=w[k]+WL
            X'<--{x[i] in X | x[i] >= x[k]}
            return WEIGHTED-MEDIUM(X')

算法分析：在对数组的每一次递归过程中，取中位数$x_k$，划分集合X和计算$W_L,W_R$的时间复杂度均为$O(n)$。最差情况下满足以下递归式：

$T(n)=T(n/2+1)+\Theta(n)$

下一次递归，划分的集合是原来的一半元素，同时还有$x_k$，因此为$T(2n+1)$。
这个递归式和快速选择(线性选择算法)的递推式接近，该算法的时间复杂度$T(n)=\Theta(n)$。

邮局位置问题的定义如下，给定权重分别为$w_1,w_2,\dotsb,w_n$的$n$个点$p_1,p_2,\dotsb,p_n$，我们希望找到一个点$p$(不一定是输入点中的一个)，使得$\sum_{i=1}^{n}{w_id(p,p_i)}$最小，这里$d(a,b)$表示点$a$和$b$之间的距离。

d. 证明：对一维邮局位置问题，带权中位数是最好的解决方法，其中，每个点都是一个实数，点$a$和$b$之间的距离是$d(a,b)=|a-b|$。

采用$x_1,x_2,\dotsb,x_n$表示$n$个点的坐标，每个点相应的权值为$w_1,w_2,\dotsb,w_n$，令$x=x_k$为带权中位数。

对于任意点$p$，我们设函数$f(p)=\sum_{i=1}^n{w_i|p-x_i|}$，我们需要找出令该函数最小值的点。令$y$是除$x$外的任意点，我们通过证明$f(y)-f(x) \geq 0$来检验带权中位数$x$是最优解。我们可以分为下面两种情况来讨论：$y > x$和 $x > y$。对于$\forall x,y$有：

$\begin{aligned} f(y)-f(x) &=\sum_{i=1}^{n}{w_i|y-x_i|} -\sum_{i=1}^{n}{w_i |x-x_i|} \\ &=\sum_{i=1}^{n}{w_i(|y-x_i|-|x-x_i|)} \end{aligned}$

1、当$y>x$时，对于上面式子中的$|y-x_i|-|x-x_i|$可以分为三种情况：

1.1、$x < y \leq x_i$

$\frac{|y-x|+|y-x_i|=|x-x_i| \quad AND \quad |y-x|=y-x} {\to |y-x_i|-|x-x_i|=-|y-x|=x-y}$

1.2、$x < x_i \leq y$

$\frac{|y-x_i| \geq 0 \quad AND \quad |x-x_i| \leq y-x} {\to |y-x_i|-|x-x_i| \geq -(y-x) = x-y}$

1.3、$x_i \leq x < y$，类似1.1

$\frac{|x-x_i|+|y-x|=|y-x_i| \quad AND \quad |y-x|=y-x}{\to |y-x_i|-|x-x_i|=|y-x|=y-x}$

解释一下上面这么写的原因，如：1.1，$d(x,x_i)==d(x,y)+d(y,x_i)$，绝对值内的减法理解为距离计算，配凑出与我们要求的式子，进行等价转换，后面方便处理。

其实对于1.1和1.3我们简单根据正负情况消去绝对值符号也行。

将前两种情况($x < x_i$)与第三种情况分开($x_i \leq x$)。。我们有：

$\begin{aligned} f(y)-f(x) &= \sum_{i=1}^{n}{w_i(|y-x_i|-|x-x_i|)} \\ &\geq \sum_{x<x_i}{w_i(x-y)}+\sum_{x \geq x_i}{w_i(y-x)} \\ &= (y-x)\left(\sum_{x \geq x_i}{w_i}-\sum_{x < x_i}{w_i}\right) \end{aligned}$

结合$x_k$的性质，我们有：

$\begin{aligned} \sum_{x_i < x}{w_i} <1/2 \quad \underrightarrow{implies} & \sum_{x_i \leq x}{w_i} \geq 1/2 \\ 和 \sum_{x_i>x}{w_i} &\leq 1/2 \\ \therefore \sum_{x \geq x_i}{w_i}-\sum_{x < x_i}{w_i} &\geq 0 \end{aligned}$

又$\because y-x >0$，$\therefore f(y)-f(x) \geq 0$

2、当$x > y$时，我们同样将$|y-x_i|-|x-x_i|$分为下面三种情况：

2.1、$x_i \leq y < x$

$\frac{|y - x_i|+|x - y|=|x-x_i|\quad AND \quad |x-y|=x-y} {\to |y-x_i|-|x-x_i|=-|x-y|=y-x}$

2.2、$y \leq x_i < x$

$\frac{|y-x_i \geq 0| \quad AND \quad |x_-x_i| \leq x-y} {\to |y-x_i|-|x-x_i| \geq -(x-y)=y-x}$

2.3、$y < x \leq x_i$,类似情况1

$\frac{|x-y|+|x-x_i|=|y-x_i| AND |x-y|=x-y} {\to |y-x_i|-|x-x_i|=|x-y|=x-y}$

和之前处理一样，分为前两种情况为$x_i < x$，第三种情况为$x \leq x_i$，我们有：

$\begin{aligned} f(y)-f(x) &=\sum_{i=1}^{n}{w_i(|y-x_i|-|x-x_i|)} \\ &\geq \sum_{x_i<x}{w_i(y-x)} +\sum_{x\leq x_i}{w_i(x-y)} \\ &=(y-x)\left(\sum_{x_i<x}{w_i}-\sum_{x \leq x_i}{w_i} \right)\\ \end{aligned}$

同上，$\because x$是带权中位数，有:

$\begin{aligned} \sum_{x_i < x}{w_i} &< 1/2 \\ 和 \sum_{x_i >x}{w_i} \leq 1/2 \quad &\underrightarrow{implies} \sum_{x_i \geq x}{w_i} > 1/2 \\ \therefore \sum_{x_i < x}{w_i}-\sum_{x \leq x_i}{w_i} &>0 \end{aligned}$

又 $\because y-x>0 \therefore f(y)-f(x)>0$。

综上：

$f(y)-f(x) \begin{cases} \geq 0 & y > x\\ > 0 & x > y \end{cases}$

因此，带权中位数$x=x_k$是一维邮局问题的最优解,得证。

e. 请给出二位邮局位置问题的最好解决方法：其中的点是$(x,y)$的二位坐标形式，点$a=(x_1,y_1)$与$b=(x_2,y_2)$之间的距离是$Manhattan$距离(曼哈顿距离/出租车距离/街区距离)，即$d(a,b)=|x_1-x_2|+|y_1-y_2|$

我们采用一对坐标来表示每个点$p_i=(x_i,y_i)$，同时每个点相应的权值为$w_i$。因此，我们的目标转变为找到一个点$p=(x,y)$使下面的函数达到最小值：

$f(x,y)=\sum_{i=1}^{n}{w_i(|x-x_i|+|y-y_i|)}$

我们可以将函数$f(x,y)$转变为两个等价的一元函数相加:

$\begin{aligned} f(x,y)&=g(x)+h(y)\\ 其中，g(x) &=\sum_{i=1}^{n}{w_i|x-x_i|} \\ h(y) &=\sum_{i=1}^{n}{w_i|y-y_i|} \end{aligned}$

我们要使$f(x,y)$取得最小值，可以单独的对每一维度进行处理，因为$g(x)$不依赖于变量$y，h(y)$不依赖于变量$x$。因此：

$\begin{aligned} \min_{x,y}{f(x,y)} &= \min_{x,y}{(g(x)+h(y))} \\ &= \min_{x} \left(\min_{y}(g(x)+h(y))\right) \\ &= \min_{x} \left(g(x)+ \min_{y}h(y) \right) \\ &= \min_{x}g(x)+\min_{y}h(y) \end{aligned}$

原先的二维问题，现在问题就转变为求2个一维最优解问题。和我们上面问题$d$一样，因此，我们只要分别求$x、y$维度上的带权中位数，设为$x_k,y_k$。最终答案记为$(x_k,y_k)$。

原文作者：007havegone

原文链接：http://007havegone.github.io/2019/08/02/算法导论思考题9-2/

发表日期：August 2nd 2019, 12:13:03 am

更新日期：August 3rd 2019, 5:38:55 pm

Next Post

Win10中shift+鼠标右键调出cmd窗口
Previous Post

算法导论练习9.3-8两个有序数组的中位数

CATALOG

1. 9-2 (带权中位数)对分别具体以正权重$w_1,w_2,\dotsb,w_n$,且满足$\sum_{i=1}^{n}{w_i=1}$的$n$个互异的元素$x_1,x_2,\dotsb,x_n$来说，带权中位数$x_k$(较小中位数)是满足如下条件的元素：
2. a. 证明：如果对所有$i=1,2,\dotsb,n$都有$w_i=1/n$，那么$x_1,x_2,\dotsb,x_n$的中位数就是$x_i$的带权中位数。
3. b. 利用排序，设计一个最坏情况下$O(nlgn)$时间的算法，可以得到$n$个元素的带权中位数。
4. c. 说明如何利用像9.3节的SELECT这样的线性时间中位数算法，在$\Theta(n)$最坏情况时间内求出带权中位数。
5. d. 证明：对一维邮局位置问题，带权中位数是最好的解决方法，其中，每个点都是一个实数，点$a$和$b$之间的距离是$d(a,b)=|a-b|$。
6. e. 请给出二位邮局位置问题的最好解决方法：其中的点是$(x,y)$的二位坐标形式，点$a=(x_1,y_1)$与$b=(x_2,y_2)$之间的距离是$Manhattan$距离(曼哈顿距离/出租车距离/街区距离)，即$d(a,b)=|x_1-x_2|+|y_1-y_2|$



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true