你的原帖对题目描述有问题.
话说,9-2的c)你怎么做的?利用线性时间的中位数算法找出带权中位数.
9-2 c)只要对9.3节的算法修改下就行了吧?
每次寻找到中间一个以后,分成两半的时候,计算前后的weight和(这个和移动一样的开销),1/2应该分到哪边就去哪边继续找.
那个post office是咋做的?
: 话说,9-2的c)你怎么做的?利用线性时间的中位数算法找出带权中位数.
c)的证明大概是,设我们找到了点p,然后给他一个位移极小量o.那么对那个和式的影响就是w(d(ppi)+o)就是w*d(ppi)+w*o恩,因为是移动,所以一边是加,一边是减.于是会发现w*o项应该是正数(保证最小),正好就满足了权重中位数的性质.
d)的解法还没想出来.
: 9-2 c)只要对9.3节的算法修改下就行了吧?
: 每次寻找到中间一个以后,分成两半的时候,计算前后的weight和(这个和移动一样的开销),1/2应该分到哪边就去哪边继续找.
d)两个维度分别求权重中位数,证明同c)
: c)的证明大概是,设我们找到了点p,然后给他一个位移极小量o.那么对那个和式的影响就是w(d(ppi)+o)就是w*d(ppi)+w*o恩,因为是移动,所以一边是加,一边是减.于是会发现w*o项应该是正数(保证最小),正好就满足了权重中位数的性质.
牛~~~之前一直没想清楚那个位移变化和咋弄.我傻了.
嗯,是到wo项不管往哪边移都为正的时候,p点就是最小了.