作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 给定n个排好序的整数阵列 找中位数
时间Wed Oct 15 07:16:31 2014
※ 引述《DJWS (...)》之铭言：
: 推 springman: 其实就是用 median of median 的演算法，只是找到 10/14 09:24
: → springman: median of median m 之後，用 binary search 找出 10/14 09:25
: → springman: 每个排序的阵列中有几个元素比 m 小，看看要找的 10/14 09:25
: → springman: median 比 m 大还是比 m 小。 10/14 09:26
: → springman: 虽然每次可能只能减少 1/4 的元素，不过没关系。 10/14 09:26
: → springman: 每次花的时间，理论值是 O(n) 找 median of median 10/14 09:27
: → springman: O(n log n) 找比 m 小的元素个数。 10/14 09:28
: → springman: 总共应该只需要花 O(log n) 次 10/14 09:28
: → springman: 每次都要使用排序好的阵列。 10/14 09:29
: → yr: 可是 problem size 不是 n^2 吗？这样上面的 n 都要换成 n^2 10/14 11:27
: 推 springman: 因为 n 个 size 为 n 的数列已经排序好了 10/14 13:12
: → springman: 要算有几个元素比 m 小时，并不是拿 n^2 个元素来比较 10/14 13:13
: → springman: 而是去每个数列做 binary search，所以时间是 O(nlogn) 10/14 13:13
: → DJWS: 第二回合要怎麽找median of median? 10/14 15:00
: 推 springman: 每一个数列是哪个范围的元素在候选名单中需要记下来 10/14 18:21
: → springman: 候选范围的资料的 median 同样可以找 median。 10/14 18:21
: 推 FRAXIS: 其实找median of median可以用排序 不影响复杂度 10/14 20:09
: → FRAXIS: 但是会比较容易作 10/14 20:09
: → DJWS: 应该是不得不排序 为了知道「减少1/4的元素」来自哪些阵列 10/14 23:04
: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我搞错了 这一句当我没说...
: → DJWS: springman的方法看起来可行 是O(n logn logn) 10/14 23:05
: ※ 编辑: DJWS (111.250.80.176), 10/14/2014 23:51:31
: 推 FRAXIS: 但是要怎麽证明一次可以删除O(n/4)个元素？ 10/15 01:27
: → FRAXIS: 因为到最後每一列的元素都不一样多 原本median of median 10/15 01:27
: → FRAXIS: 的证明法好像不能直接套用 10/15 01:28
昨天睡觉时用力想了一阵
事实上不需要跑 binary search，也不必跑 partition
这边重新整理一下
给定 n 个长度 n 已排序阵列，找第 k 小的元素
每个阵列都有两个指标 low = 0 和 high = n-1 O(n)
每个阵列的大小 size = high - low + 1 O(n)
每个阵列的中位数 array[(low + high) / 2] O(n)
上述n个中位数的中位数，设为x O(n) 套用中位数演算法
注意到上述n个中位数，有一半比x小 (大)
注意到其所对应的阵列，每个阵列都有一半比x小 (大)
注意到有1/4的元素比x小 (大) 只有第一回合!
依序扫描n个中位数 O(n)
比x小(大)的中位数
其所对应的阵列，预计删除小(大)的那一半
也就是 low = (low + high) / 2 + 1; O(1)
(或者 high = (low + high) / 2 - 1;)
预计更新阵列大小为 size = high - low + 1 O(1)
累计欲删除的元素数量 y (小的那些) O(1)
如果第k个元素小於等於 y，那麽就删除最大的那 1/4，下个回合找第 k 小的元素
否则就删除最小的那 1/4，下个回合找第 k = Σsize - y 大的元素
得再扫描一遍n个中位数，进行实际删除
总共 O(logn) 个回合 n^2元素每回合减少1/4 的话...
总共 O(logn) 个回合 每回合有一半的阵列少了一半
时间复杂度 O(n logn)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.79.164
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413328594.A.3F3.html
※ 编辑: DJWS (111.250.79.164), 10/15/2014 07:43:07
1F：推 FRAXIS: 如果每回合都有一半阵列被删除一半 那顶多只有O(lg n)回合 10/15 07:42
2F：→ DJWS: 是这样吗? 要怎麽证明? 10/15 07:43
3F：→ DJWS: 好像是你说的这样没错 我改一下 10/15 07:47
※ 编辑: DJWS (111.250.79.164), 10/15/2014 07:47:28
4F：→ DJWS: 然後这个方法也可以套用到已排序二维阵列 上述步骤都是O(1) 10/15 07:51
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我又讲错了 这句话当我没说...
5F：推 FRAXIS: 太强啦~~ 10/15 07:56
6F：→ DJWS: 感谢springman的想法 10/15 07:59
※ 编辑: DJWS (111.250.79.164), 10/15/2014 08:06:39
7F：推 springman: 您们已经想得比我多了 ^_^。 10/15 08:17
8F：→ DJWS: FRAXIS 这题目有人做过吗？ 10/15 08:29