Поиск кортежа со всеми элементами, превышающими заданный кортеж, эффективно

Question

Рассмотрим следующий список кортежей: [(5,4,5), (6,9,6), (3,8,3), (7,9,8)]

Я пытаюсь разработать алгоритм, чтобы проверить, существует ли по крайней мере один кортеж в списке, где все элементы этого кортежа больше или равны заданному кортежу (игла).

Например, для данного кортежа (6,5,7) алгоритм должен возвращать значение True, поскольку каждый элемент в данном кортеже меньше первого кортежа в списке, т. Е. (5,4,5). Однако для данного кортежа (9,1,9) алгоритм должен возвращать False, поскольку в списке нет кортежа, где каждый элемент больше заданного кортежа. В частности, это связано со вторым элементом 1 данного кортежа, который меньше, чем второй элемент всего кортежа в списке.

Наивный алгоритм будет циклически перебирать кортеж в списке один за другим и прокручивать элемент кортежа во внутреннем цикле. Предполагая, что существует n кортежей, где каждый набор имеет m элементов, это даст сложность O (nm).

Я думаю, можно ли иметь алгоритм для выполнения задачи с меньшей сложностью. Допускается предварительная обработка или любая воображаемая структура данных для хранения данных!

Моя первоначальная мысль заключалась в том, чтобы использовать какой-либо вариант бинарного поиска, но я не могу найти структуру данных, которая позволяет нам не возвращаться к наивному решению, как только мы устранили некоторые кортежи, основанные на первом элемент, что означает, что этот алгоритм потенциально может быть O (nm) в конце.

Спасибо!

Answer 1

Этот вид проблемы адресуется системами spatial indexing. Существует много структур данных, которые позволяют эффективно выполнять ваш запрос.

Answer 2

Пусть S - topologically-sorted копия исходного набора из n каждого m-кортежа. Затем мы можем использовать бинарный поиск для любого тестового кортежа в S по стоимости O (m ln n) для поиска (из-за не более lg n поисковых слоев с не более m сравнений на каждый слой).

Обратите внимание, что существуют такие кортежи P, Q в S, что P ≤ Q (т. Е. Ни один элемент из Q не будет меньше соответствующего элемента P). Тогда кортеж Q можно удалить из S. На практике это часто может сократить размер S до небольшого кратного m, что даст производительность O (m ln m); но в худшем случае вообще не будет уменьшать.