我有一个偏序集,说A = [x1, x2, ...],这意味着每一个xi和xj集合中的,(恰好)的四种可能性之一为真:xi < xj,xi == xj,xi > xj,或xi与xj所无法比拟的.
我想找到的最大元素(即,这些元素xi是针对那些还没有元素xj用xi < xj).什么是有效的算法(最小化比较次数)？我尝试构建DAG并进行拓扑排序,但只是构建图形需要进行O(n ^ 2)次比较,这太多了.
我在Python中这样做,但如果你不知道它我可以读其他语言,或伪代码.
无论你做什么,似乎最坏的情况是O(n ^ 2).例如,如果没有可比较的元素,则需要将每个元素与每个其他元素进行比较,以确定它们都是最大的.
如果你允许O(n ^ 2),因为排序是可传递的,你可以只通过集合进行一次传递,保留到目前为止最大的所有元素的列表; 每个新元素都会清除任何<it的最大元素,如果它不是<任何最大元素,则会被添加到最大列表中.