Эффективный способ найти парные заказы?

Допустим, у меня есть три массива a, b и c одинаковой длины N. Элементы каждого из этих массивов взяты из полностью упорядоченного набора, но не отсортированы. У меня также есть две индексные переменные, i и j. Для всех i != j я хочу подсчитать количество пар индексов, таких как a[i] < a[j], b[i] > b[j] и c[i] < c[j]. Есть ли способ сделать это менее чем за O(N ^ 2) временной сложности, например, путем творческого использования алгоритмов сортировки?

Примечания: Идея этого вопроса заключается в том, что если у вас есть только два массива, a и b, вы можете найти количество пар индексов, таких что a[i] < a[j] и b[i] > b[j] за O(N log N) с сортировкой слиянием. Я в основном ищу обобщение до трех массивов.

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


sorting algorithm statistics math theory
person dsimcha    schedule 19.01.2011    source источник
comment
Вам нужен один массив, когда этот алгоритм завершится? Например. массив, в котором хранятся все элементы из a, b и c в отсортированном порядке?   -  person David Weiser    schedule 19.01.2011
comment
Не могли бы вы привести пример того, что такое четко определенный общий порядок?   -  person David Weiser    schedule 19.01.2011
comment
Полный порядок на множестве поддерживает антисимметрию, транзитивность и тотальность; см. статью Wiki для получения дополнительной информации. en.wikipedia.org/wiki/Total_order   -  person Tim    schedule 19.01.2011
comment
@David: Все, что я хочу, когда алгоритм завершит работу, — это одно целое число, представляющее сколько пар i, j с этим свойством.   -  person dsimcha    schedule 19.01.2011
comment
Если каждый массив имеет общий порядок, то для всех i ‹= j, a[i] ‹= a[j], b[i] ‹= b[j], c[i] ‹= c[j]. Это правильно? В данном случае это не ответ, тогда |a| + |с| (поскольку количество раз b[i] › b[j] равно 0)?   -  person David Weiser    schedule 19.01.2011
comment
@David: элементы в массивах являются членами полностью упорядоченного множества, т. е. их можно сортировать, но нельзя.   -  person Fred Foo    schedule 19.01.2011
comment
@larsmans: вопрос говорит о том, что элементы каждого массива имеют общий порядок. Если то, что вы говорите, верно, то я бы рекомендовал переформулировать вопрос так: элементы каждого массива происходят из набора, который имеет общий порядок (но сами массивы не отсортированы). Я также удалил свой ответ в в свете этого и жду, когда спрашивающий переформулирует вопрос.   -  person David Weiser    schedule 19.01.2011
comment
@ Дэвид, извини, я должен был сказать, что для каждого массива элементы являются членами некоторого полностью упорядоченного набора. Однако формулировка @dsimcha является более обычным способом выразить это.   -  person Fred Foo    schedule 19.01.2011
comment
Есть ли причина, по которой вы выбрали > для одного массива, а < для остальных? Кажется, что это произвольный выбор, поскольку вы можете просто изменить порядок.   -  person comingstorm    schedule 19.01.2011
comment
@comingstorm: Нет, нет причин. Это произвольный выбор. На самом деле, тот факт, что я выбрал >, означал, что это совершенно произвольно.   -  person dsimcha    schedule 19.01.2011
comment
ваш вопрос лучше подходит для cstheory.stackexchange.com.   -  person Daniel A. White    schedule 19.01.2011
comment
@Daniel Нет, этот сайт предназначен для вопросов исследовательского уровня.   -  person moinudin    schedule 19.01.2011

Ответы (1)


arrow_upward
6
arrow_downward

Сортируя массив a и одновременно переставляя массивы b и c, мы можем предположить, что a[i] ‹ a[j] ‹=> i ‹ j. Итак, нам нужно найти количество пар (i,j), таких что i ‹ j, b[i] > b[j] и c[i] ‹ c[j]. Давайте рассмотрим (b[i], c[i]) как точку на плоскости. Добавляем точки одну за другой. Каждый раз, когда мы добавляем точку (b[j], c[j]), сначала мы подсчитываем количество уже добавленных точек (i ‹ j), таких что b[i] > b[j] и c[i] ‹ c [ж]. Затем добавляем точку j и переходим к следующей. Сумма чисел, полученных на каждом шаге, и есть наш результат.

Теперь кажется, что такого рода запросы могут быть выполнены двумерным деревом сегментов: http://en.wikipedia.org/wiki/Segment_tree Стоимость одной итерации составит O(log^2 n), а общая сложность — O(n log^2 n).

(Обратите внимание, что здесь я предполагаю, что элементы массивов являются числами. Это нормально, потому что с помощью сортировки мы всегда можем заменить элементы массива числами от 1 до n так, чтобы порядок был сохранен.)

Редактировать: на самом деле достаточно более простой структуры, называемой деревом Фенвика или бинарным индексированным деревом. См. эту ссылку: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#2d

person adamax    schedule 19.01.2011