※ 引述《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)