Алгоритм поиска совпадающих элементов

Question

Нам дают таблицу_1: 6 3 2 5 2, table_2: 7 4 1 6 8, table_3: 15,14,5,4,9. Число элементов в таблице_1 равно количеству элементов в таблице_2. Как найти FAST, если в таблице_1, table_2 есть такие элементы, что для конкретного элемента из таблицы_3: table_3 [i] = table_1 [k] + table_2 [p].

Пример: 9 = table_3 [4] = table_1 [1] + table_2 [3];

Я попытался выполнить сортировку и алгоритм binary_search, чтобы решить эту проблему:/но это дает слишком медленное решение.

Answer 1

Вы говорите, что O (nlogn) работает слишком медленно. Вы имеете в виду, что ваша конкретная реализация некоторого решения O (nlogn) была слишком медленной или любой рост O (nlogn) будет слишком медленным? Если это последнее дело, то вы, как сказал бы мой сын, обжаривали.

Давайте рассмотрим это с точки зрения структуры данных и анализа алгоритмов. Если вы разрешаете table_1 и table_2 оставаться неупорядоченными, вам необходимо сделать n^2 попарных сравнений. Поэтому table_1 и table_2 должны быть отправлены в какой-то процесс упорядочения.

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

Теперь вы можете создавать миниатюры в линейном времени, но table_3 - это O (n) в размере, как table_1 и table_2. Вы по-прежнему проигрываете, так как вам все равно нужно выполнить n * n/2 средних сравнений, чтобы проверить значения таблицы_3 на комбинацию пар из table_1 и table_2.

Каковы временные ограничения для этого решения? 1 мс, 1 сек? Есть ли какая-то структура или предварительные знания о данных, которые могут позволить решение, использующее данные? Если нет, я не вижу решения.