作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 给定n个排好序的整数阵列 找中位数
时间Tue Oct 14 07:56:19 2014
※ 引述《FRAXIS (喔喔)》之铭言：
: 问题：给定 n 个已排序整数阵列，每个阵列长度为 n
: 找出 n^2 个元素中的中位数。
: 在网路上有找到几个讨论
: http://ppt.cc/PMvU
: http://ppt.cc/JE1s
: (这是变形，给定一个n by n矩阵，每行每列都排序，找中位数)
: 但是我觉得他们的解法到最後都变成O(n^2 lg n)。
: 而如果忽略掉每个阵列都已经排序的性质，直接在 n^2 个元素中找中位数，
: 因为找中位数可以在线性时间内完成，
: 所以在 n^2 个元素内找中位数只需要O(n^2)的时间，也比网页上的解答好。
: 有没有比O(n^2)快的方法来解决这问题呢？
应该很难吧！
资料有 n^2 笔，然後时间复杂度是 O(n^2)，基本上已经是 linear time
要低於线性时间
要嘛略过一些资料
要嘛问题本身有很强的数学性质，可以直接推导答案
在这个问题当中，上面两种策略似乎都行不太通
考虑 median-of-median algorithm 的第一回合
由於给定资料是 n 条已排序阵列，所以第一回合可以省下很多工夫，可以很快做完
但是找到中位数的中位数之後
接下来，还有可能是中位数的资料，约占全部的3/4
第二回合还是得处理 3/4 * n^2 这麽多资料，依旧是 O(n^2) 级别
即便我们已经知道 n 条已排序阵列，但是它的功效只能帮助我们略过 1/4 的资料
再加上中位数没有什麽好的数学性质，尤其是可以用於精确计算的的数学性质
所以我觉得很难达成！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.64.234
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413244582.A.286.html
※ 编辑: DJWS (111.250.64.234), 10/14/2014 08:02:10
1F：推 springman: 其实就是用 median of median 的演算法，只是找到 10/14 09:24
2F：→ springman: median of median m 之後，用 binary search 找出 10/14 09:25
3F：→ springman: 每个排序的阵列中有几个元素比 m 小，看看要找的 10/14 09:25
4F：→ springman: median 比 m 大还是比 m 小。 10/14 09:26
5F：→ springman: 虽然每次可能只能减少 1/4 的元素，不过没关系。 10/14 09:26
6F：→ springman: 每次花的时间，理论值是 O(n) 找 median of median 10/14 09:27
7F：→ springman: O(n log n) 找比 m 小的元素个数。 10/14 09:28
8F：→ springman: 总共应该只需要花 O(log n) 次 10/14 09:28
9F：→ springman: 每次都要使用排序好的阵列。 10/14 09:29
10F：→ yr: 可是 problem size 不是 n^2 吗？这样上面的 n 都要换成 n^2 10/14 11:27
11F：推 springman: 因为 n 个 size 为 n 的数列已经排序好了 10/14 13:12
12F：→ springman: 要算有几个元素比 m 小时，并不是拿 n^2 个元素来比较 10/14 13:13
13F：→ springman: 而是去每个数列做 binary search，所以时间是 O(nlogn) 10/14 13:13
14F：→ DJWS: 第二回合要怎麽找median of median? 10/14 15:00
15F：推 springman: 每一个数列是哪个范围的元素在候选名单中需要记下来 10/14 18:21
16F：→ springman: 候选范围的资料的 median 同样可以找 median。 10/14 18:21
17F：推 FRAXIS: 其实找median of median可以用排序 不影响复杂度 10/14 20:09
18F：→ FRAXIS: 但是会比较容易作 10/14 20:09
19F：→ DJWS: 应该是不得不排序 为了知道「减少1/4的元素」来自哪些阵列 10/14 23:04
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我搞错了 这一句当我没说...
20F：→ DJWS: springman的方法看起来可行 是O(n logn logn) 10/14 23:05
※ 编辑: DJWS (111.250.80.176), 10/14/2014 23:51:31
21F：推 FRAXIS: 但是要怎麽证明一次可以删除O(n/4)个元素？ 10/15 01:27
22F：→ FRAXIS: 因为到最後每一列的元素都不一样多 原本median of median 10/15 01:27
23F：→ FRAXIS: 的证明法好像不能直接套用 10/15 01:28