算法----中位数算法的妙用(更新中) - 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