x*j
发帖数: 271 | 1 我这里说的经典的top-k element问题就是给一列没排好序的数，然后找到top-k个最大
的元素，用partition-base的算法average是 O(n), worst time O(n^2)
现在有这么一个问题，给一列object，和一个compare function, 在 O(1)的时间里对
pair a,b这个function会告诉3个结论，1 a b, 3 cannot tell
partial order 还是成立的 i.e. aa
top-k的定义是如下，返回这列object的一个子集，使得对于任意一个没有返回的
object a，在返回的子集里至少有k个object b1, b2, ..., bk, s.t. a
同时 返回的子集的大小最小。
最后这个大小最小的条件是为了确保解唯一和有意义，否则的话总是可以返回所有的
object从而使得第一个条件成立。
我的问题是，我知道O(n^2)的算法是可以解的，不是非常naive但很trival。 我不知道
这个是不是就是lower bound | T*****9
发帖数: 2484 | 2 可以先sort，然后找第k个数。。。
k.
【在 x*j 的大作中提到】
: 我这里说的经典的top-k element问题就是给一列没排好序的数，然后找到top-k个最大
: 的元素，用partition-base的算法average是 O(n), worst time O(n^2)
: 现在有这么一个问题，给一列object，和一个compare function, 在 O(1)的时间里对
: pair a,b这个function会告诉3个结论，1 a b, 3 cannot tell
: partial order 还是成立的 i.e. aa: top-k的定义是如下，返回这列object的一个子集，使得对于任意一个没有返回的
: object a，在返回的子集里至少有k个object b1, b2, ..., bk, s.t. a: 同时 返回的子集的大小最小。
: 最后这个大小最小的条件是为了确保解唯一和有意义，否则的话总是可以返回所有的
: object从而使得第一个条件成立。
| x*j
发帖数: 271 | 3 拜托，怎么sort? 只有o(n^2)的sort算法work | l******e
发帖数: 470 | 4 很多sort算法O(nlogn)
heap sort， merge sort。。。。
而且你的问题根本不用sort，有O(n)的算法，
http://crystal.uta.edu/~gdas/Courses/Courses/Spring2008/Algo2/L4.ppt
【在 x*j 的大作中提到】
: 拜托，怎么sort? 只有o(n^2)的sort算法work
| c*****t
发帖数: 1879 | 5 我觉得 LZ 的问题写很奇怪。已经说了是 top-k 的问题，还扯上什么
子集的大小。
【在 l******e 的大作中提到】
: 很多sort算法O(nlogn)
: heap sort， merge sort。。。。
: 而且你的问题根本不用sort，有O(n)的算法，
: http://crystal.uta.edu/~gdas/Courses/Courses/Spring2008/Algo2/L4.ppt
| x*j
发帖数: 271 | 6 我当然知道有O(n)的算法去找到k个最大的数，是quicksort的partition部分部分的一
个改版，在最开头我已经说的很清楚了。
这个问题的原因在于大于和小于的关系还在，但等于的关系没了。
举例说明 假设有3个单词a b c
a和b之间的 edit distance是 1 b和c之也是1，但a和c之间可能就是2，如果我们定义
edit distance是1或者0的都是不可分的，但二以上就有一个大小于关系，我们可以说a
这个topk的问题是要求返回一个子集，对于没有返回的任何元素，这个子集里都存在着
k个比它大的，但这个子集可以存在和它约等于的元素。因为对于元素a和b，如果a约等
于b，那么比a大的元素不一定比b大。所以这个返回的集合是可能包含不只k个元素的。
我很欢迎有帮助的讨论。对于问题不理解我也很愿意继续澄清，但是请注意的是这里没
有等于只有约等于，所以那些对于integer的排序的算法比如quicksort mergesort
heapsort，它们的复杂度不适用于这个问题。
我知道mergesort的复杂度是O(n^2logn)在这个 | T*****9
发帖数: 2484 | 7 ???没学过排序
【在 x*j 的大作中提到】
: 拜托，怎么sort? 只有o(n^2)的sort算法work
| x*j
发帖数: 271 | 8 学过排序,不过，如果只有约等于没有等于的话,那比较的时候就没有办法按照等于的方
式比较了. | x*j
发帖数: 271 | 9 O(nlogn)的排序算法在这个题目里没办法work,因为只有partial order | c*****t
发帖数: 1879 | 10 你的标点符号得弄全，该有句号的时候得加上。我说读起来怎么这么费劲呢。
比如 cannot tell partial order ... 我看了半天才明白 cannot tell 后面
就是句号，partial order 已经是另外一句子的开头。
你这个 cannot tell 是指没法算出来，并不表明没有吧。也就是 a 可能小于
b 也可能大于 b 吧。否则你的问题没道理。
k.
【在 x*j 的大作中提到】
: 我这里说的经典的top-k element问题就是给一列没排好序的数，然后找到top-k个最大
: 的元素，用partition-base的算法average是 O(n), worst time O(n^2)
: 现在有这么一个问题，给一列object，和一个compare function, 在 O(1)的时间里对
: pair a,b这个function会告诉3个结论，1 a b, 3 cannot tell
: partial order 还是成立的 i.e. aa: top-k的定义是如下，返回这列object的一个子集，使得对于任意一个没有返回的
: object a，在返回的子集里至少有k个object b1, b2, ..., bk, s.t. a: 同时 返回的子集的大小最小。
: 最后这个大小最小的条件是为了确保解唯一和有意义，否则的话总是可以返回所有的
: object从而使得第一个条件成立。
| c*******h
发帖数: 1096 | 11 你的问题是半序集排序，跟一般的排序不一样（因为没有全序），是一个比较难的问题
如果有全序，那比较容易，用线性的时间找到第k个元素，然后将数组扫一遍就得到k个
最大元了
如果只有半序，比较容易想到的是拓扑排序，然后想办法找到大于等于k个最大元。但
是不可避免的会碰到n^2的复杂度。
今年SODA有一篇paper是讲半序排序的，给了一个理论的lower bound；还给了一个算法
，分析了这个算法的复杂度。
k.
【在 x*j 的大作中提到】
: 我这里说的经典的top-k element问题就是给一列没排好序的数，然后找到top-k个最大
: 的元素，用partition-base的算法average是 O(n), worst time O(n^2)
: 现在有这么一个问题，给一列object，和一个compare function, 在 O(1)的时间里对
: pair a,b这个function会告诉3个结论，1 a b, 3 cannot tell
: partial order 还是成立的 i.e. aa: top-k的定义是如下，返回这列object的一个子集，使得对于任意一个没有返回的
: object a，在返回的子集里至少有k个object b1, b2, ..., bk, s.t. a: 同时 返回的子集的大小最小。
: 最后这个大小最小的条件是为了确保解唯一和有意义，否则的话总是可以返回所有的
: object从而使得第一个条件成立。
| x*j
发帖数: 271 | 12 就是半序集排序啊,实际上我只找到了O(n^2)的算法, 没找到更低的了。 |
|
