算法----中位数算法的妙用(更新中) - L.J.SHOU的专栏 - 博客频道 - CSDN.NET
中位数算法O(N)有许多妙用，能够在一些场合下替代 排序O(NlgN)
1. 中位数算法
求N个数组中的中位数即求第n/2大的数
算法导论中给出了两种求第k大的数的算法
算法1： 随机算法 平均复杂度O(n)
思路：利用quicksort的随机版本的partition, 将数组分成2部分：
if 左边部分数目<k, 则在右边递归搜索
else if 左边的数> k， 则在左边递归搜索
else return a[partition];
算法2： 确定性算法 最坏复杂度O(n)
2. 三个例子
例题1：带权中位数
n个数x[1], x[2],..., x[n], 各自带有一个权重， w[1], w[2], ..., w[n], w的总和是1
求x[k]满足 所有满足x[i] < x[k]的元素的权重之和< 1/2， 所有满足x[i] > x[k]的元素的权重之和 >=1/2;
算法1： 先排序O(NlgN)， 从前往后遍历数组，找到第一个x[k], 使得前k个元素的权重之和>=1/2, return x[k]
算法2： 分治: 用中位数算法，将问题的规模减半
思路： 其实这个题并不需要排序，我们仅仅需要找到 n个数中较小的K(未知)个数的集合，使得它的和<1/2, 其他元素的和>=1/2, 具体这两个集合中的数并不需要排序。考虑用中位数算法来找这个集合。
伪代码： WeightedMid(a, i, j, w)
mid = Select(a, i, j) //中位数算法
left_sum = w[i]+w[i+1]+...+w[mid-1]; //左半部分数组的权重和
right_sum = w[mid+1]+w[mid+1]+...w[j];
if left_sum >=w, return WeightedMid(a, i, mid-1, w);
elseif right_sum >w, return WeightedMid(a, mid, j, w-left_sum);
else return x[mid];
T(n) = T(n/2) + O(n)
例题2： 部分背包问题：
一个窃贼去一家商店偷窃，有n件商品： 第i件物品值vi元，重wi榜（vi, wi都是整数），他的背包最多只能装下W榜物品，
每件商品他可以选择一部分带走，而不像0-1背包问题。问他最多能带走多贵的物品？
分析： 由于部分背包问题允许仅拿走物品的一部分，物件更像是金粉，可证明其具有贪心的性质。
算法1： 贪心
按照每榜的价值进行排序，然后由价值的大小依次往包里装，直到重量为W。
算法复杂度是 O(nlgn).
能不能将其复杂度降低到线性呢？
注意到，无论是动态规划还是贪心，其实都具有问题可分（decomposed)的性质, 也就是可以考虑用分治（divide-and-conquer)。
要构造O(n)的算法，首先想到 T(n) = T(n/2) + O(n)，
--------------- 在O(n)的时间内把问题的规模降为一半，那么就得到了一个O(N)的算法。
分析：
贪心算法时间复杂度主要是排序，可以不排序吗？
可以。排序只是为了找出那些单价高的物品集合，所以我们并不需要把所有的单价进行排序。
我们只需要找到背包所能装得下的那部分单价较高的物品即可。这类似于在数组中找前k大的k个数（复杂度是O(N)）.
因此使用排序我们其实做了多余的比较。
目标：一分为二，而且要找的是前k大的k个数（k未知），
Bingo！ 先找出中位数!
算法2：
n个物品的单价数组： A[1:n]
找出其中位数，将数组分成3个部分： A{单价高于中位数} B{单价等于中位数} C{单价小于中位数}
注意到 {A}, {A+B}， {C}的规模<=n/2
下面分三种情况：
1. 若集合A中的物品总质量 >= W， 递归在A中解部分背包问题
2. 若集合A中的物品总质量 < W, 且集合{A+B}中的物品总质量 >=W, 将A中物品全部装入包中，剩余的从B中随便取即可
3. 若集合{A+B}中的物品总质量 < W, 将A和B中的物品全部放入背包中，剩余的质量递归地在集合C中求解
复杂度分析：
求中位数复杂度是 O（N）, 上述三种情况中除了子问题外，也顶多花O（N）时间，
T(n) <= T(n/2) + O(n)
所以 T(n) = O（n)
例3：
N个数中有一个数出现的次数大于1/2
算法1： 先排序，再扫描一次数组，记录出现的次数 O(nlgn)
算法2: 这一问题其实也不需要排序。中位数即为所求。O(n)
Read full article from 算法----中位数算法的妙用(更新中) - L.J.SHOU的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment