Алг-м поиска мин. эл-ов в частично упорядоченном множестве

[_hum_]

Дан массив элементов, для которых имеется функция попарного сравнения с результатами "меньше", "равно", "больше", "не сравнимы". Есть ли какой-нибудь алгоритм пометки всех минимальных элементов этого массива с порядком сложности, меньшим квадратичного?

[Circiter]

Обычная сортировка, $\mathcal{O}(n\log n)$. Выделить группу одинаковых элементов в начале отсортированного массива $+\mathcal{O}(n)$ (т.е. можно игнорировать).

[_hum_]

Что-то я не понимаю...
Во-первых, как-то не очевидно, что обычные методы сортировки будут работать на частично-упорядоченых множествах (как будет работать та же сортировка выбором, когда для какой-то пары элементов функция сравнения даст "не сравнимы"?).
А во-вторых, даже если обычная сортировка применима, то все равно же будет неясно, где кончается одна отсортированная цепь (линейно упорядоченное подмножество) и начинается другая, чтобы можно было выделить минимальные элементы.

[Circiter]

Ага, приношу извинения; я, оказывается, вас совершенно не правильно понял. :)

[Circiter]

Кстати, я всё-таки слышал краем уха о работах по оценке сложности сортировки частично-упорядоченных множеств. Очевидно, речь идет о множествах, какого-то особого вида. В общем случае же, не представляю как можно достичь менее чем квадратичной асимптотики. Ну вот, к примеру, при топологической сортировке всё-равно же придется все элементы отношения частичного порядка проверить, т.е. все пары элементов сортируемого множества, $\mathcal{O}(n^2)$...

[worm2]

Действительно, пусть все элементы попарно несравнимы, за исключением двух.
Поиск этой пары выливается в $\mathcal{O}(n^2)$.

[_hum_]

Похоже на то. Спасибо.

Кстати, интересно, при каком минимальном порядке сложности по дополнительной памяти можно порядок сложности по времени понизить до $O(n \log n)...$

[Pavia]

Перечитал так и не понял вопроса.
Отвечаю по классике.
Для поиска минимального элемента в массиве надо O(n) операций сравнения.
Для пометки тоже надо O(n)
Как результат для решения данной задачи надо O(n)

[Circiter]

2Pavia

Цитата:

Перечитал так и не понял вопроса.

Как я сам понял, задачка топикстартера может быть переформулирована в, имхо, чуть более наглядных терминах перечисления источников в орграфе, индуцированным данным частичным порядком.

2_hum_

Цитата:

при каком минимальном порядке сложности по дополнительной памяти можно порядок сложности по времени понизить

Была бы подходящая структура данных с метками на вершинах с указанием in- и out-степеней, так и вообще бы за линейное время все искалось... :)

[maxal]

Парочка статеек по теме:

Parallel Computation of the Minimal Elements of a Poset

Sorting and Selection in Posets