楼主:
chz (稻草人骑士)
2014-10-15 18:31:28※ 引述《dreamoon (大笨蛋小月唷!)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 依序扫描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 大的元素
: 对于这里我有点困惑
: 若k<=y，删除叫大的那些数是没问题的，因为那些数一定比第k个数还大
: 但是当k>y时，真的能删除较小的那一部分嘛?
: 例如说现在有7*7的矩阵
: 1, 2, 3, 4, 5, 6, 7
: 8, 9,10,11,12,13,14
: 15,16,17,18,19,20,21
: 22,23,24,25,26,27,28
: 29,30,31,32,33,34,35
: 36,37,38,39,40,41,42
: 43,44,45,46,47,48,49
: 并且我要找的数是第17小的数
: 但比较小的那部分却只有16个数
: 于是按照这个算法我们就会把真正的第17小的数给移除了0.0(我没理解错的话...)
其实把DWJS的方法稍微改一下就可以了。
对于目前的n条序各列改中位数 O(1)
n个中位数找中位数(MoM) O(n)
对每一条序列用binary search找比MoM大和小各有多少个 O(n logn)
会有 n_l个比MoM小，n_r个比MoM大，选择目标的那一边。
更新序列的 head和 tail O(1)
看把n_l或n_r被砍掉的部份算到全部被移掉的N_L和N_R中。
重复以上动作直到MoM收敛。
这个动作至多进行 O(log n)次，分析如下：
考虑n条长度为n的序列
每次动作至少有n/2条会被移除一半
也就是说，至多只要 2 log n次，所有的序列都会只剩下一个元素。
因此在经过 O(n log n log n)的时间后,还剩下O(n)个元素要找第k大的数。
再加上最后的O(n)，时间复杂度还是 O(n log n log n)。
ps. 跑实验的结果 random input大概只需要 log n个 iteration就会收敛了。
几乎不会跑到 2 log n个iteration。