求部分有序的数列的中位数

阅微客栈 » 头脑风暴

求部分有序的数列的中位数

(9 posts)

发起于 1 年之前，作者 zhang
最新回复来自于 lemonutzf

Tags:

zhang
神

一个 $n\times n$ 的矩阵数列，若此序列每一列都是增序的，求这 $n^2$ 个数的中位数。

发布于 1 年之前 #
wsamc
沙茶

顺便说一下，这个问题的算法时间复杂性下界是 $O(n\log n)$ ，知道的一个算法可以做到 $O(n\log ^2 n)$ 。

---------------
写错了，已知的一个算法应该是 $O(n\log ^3 n)$ 的时间。

发布于 1 年之前 #
szuxjq
Member

那个算法怎么做的？

发布于 1 年之前 #
king
Member

每列是有序的，那么可以将每列作为一个顺序串，使用败者树进行排序，时间复杂度应该是 $O(n^2\log n)$ 里面2是平方
不知道管理员说的是那个复杂度是用什么方法实现的。

发布于 1 年之前 #
wsamc
沙茶

其实对于任意的N个数求中位数，已知算法可以在 $O(N)$ 时间内完成，因此，对这个问题 $O(n^2)$ 完成是没有问题的。

$O(n\log^3n)$ 的算法基本思路是这样的：
1.先取每个序列的中位数组成集合 $A=\{a_1,...,a_n\}$ ，用已知的算法在 $O(n)$ 时间内找到 $A$ 的中位数，计为 $a$ ,
2.在所有序列中，用折半查找找出 $a$ 所处的位置，从而算出 $a$ 在所有数中的位置，
3.如果 $a$ 恰好是中位数，搞定，输出 $a$ ；
如果 $a > n^2/2$ ，将所有 $\{i|a_i \geq a}$ 所对应的序列长度减半（因为这些序列中有一半的数 $\geq a_i \geq a$ 从而不可能是中位数）；
如果 $a < n^2/2$ ，将所有 $\{i|a_i \leq a}$ 所对应的序列长度减半（因为这些序列中有一半的数 $\leq a_i \leq a$ 从而不可能是中位数）；
4.对于剩下的所有长度 $>1$ 的序列，重复1-3。

由于每次循环长度大于1的序列有一半被减半，并且对于长为 $n$ 的序列最多经过 $O(\log n)$ 次减半后长度变为1，因此以上循环最多 $O(\log^2n)$ 次以后所有序列长度为1从而问题可以简单解决。而每次循环的时间（包括找中位数的中位数，确定该中位数在所有数中的位置，对所有长度非1的序列判断是否要减半）为 $O(n\log n)$ 。所以总时间复杂性为 $O(n\log^3 n)$ 。

一些细节，比如更新当前循环中所有数的中位数在当前剩余数中的位置、最多需要 $O(\log^2 n)$ 次循环等等，还需要仔细的考虑甚至归纳证明，这里就不讨论了。

最后，提一下能想到的这个问题的时间复杂性下界 $\Omega(n\log n)$ ：
在decision tree模型下，在n个序列中找中位数，需要区分的状态数，相当于对n个序列确定 $index_i,i\in n$ ，使得中位数 $q$ 恰好满足 $a^i_{index_i}\leq q\leq a^i_{index_i+1}$ 时所有可能的index方法的个数，也就是 $\sum_i ^n l_i = n^2/2$ 并且 $0\leq l_i\leq n_i$ 的解的个数。而这个数目不小于对前一半的序列随便在0到n之间取值的数目（因为这样的取值一定可以通过调整后一半的index使得方程有解），所以总状态数不小于 $\Omega(n^{n/2})$ ，从而需要的比较次数至少为其对数 $\Omega(\log(n^{n/2}))=\Omega(n\log n)$ 。

欢迎给出任何idea和comment，无论是算法还是lower bound。

发布于 1 年之前 #
szuxjq
Member

嗯，看了管理员的阐释，似乎就是这样的了。

发布于 1 年之前 #
szuxjq
Member

类似有个问题，两组长为n的各自有序的数组，找到在两者里面第k大的成员。是不是O(logk)？

发布于 1 年之前 #
lemonutzf
Member

wsamc 的算法还可进一步优化：如果sum(a的位置) > n^2/2，将所有 {i | ai>=a } 所对应的序列长度减半. 可改成：将所有 {i | ai>=a } 和 {i | i< a的位置-(sum(a的位置)-n^2/2) } 剪去

发布于 7 月之前 #
lemonutzf
Member

另外，两组长为n的各自有序的数组，找到在两者里面第k大的成员，时间复杂度是lgk * lgk

发布于 7 月之前 #

该主题的 RSS Feed

你必须登录后发帖。

阅微客栈

阅微客栈 » 头脑风暴

求部分有序的数列的中位数

回复