Вычисление множества пересечений в линейном времени?

Существует ли алгоритм, который, учитывая два набора, вычисляет их пересечение в линейном времени?

Я могу запустить две циклы for для проверки всех пар элементов, записывающих элементы, которые я нахожу в обоих наборах. Однако время выполнения будет равно O (n ²). Как это сделать в O (n) времени?

Ответ 1

Это зависит от реализации вашего набора.

Если у вас есть хэш-набор (O (1) поиск), то подход, обозначенный всеми другими плакатами, верен. Итерации по всем элементам в первом наборе. Если он во втором наборе, то добавьте его в результат. Это выполняется в O (n) времени.

Если у вас есть набор деревьев (O (lg n)), то этот подход будет работать, но он работает в O (n lg n) времени. Ты можешь лучше; существует O (n) решение. Я предполагаю, что у вас есть своего рода итератор, который может пересекать элементы двух наборов в порядке возрастания. Если вы это сделаете, тогда вопрос будет "задан двумя списками в отсортированном порядке, найдите их пересечение". Это можно сделать, используя модифицированную версию алгоритма, который вы используете для объединения двух диапазонов. Идея состоит в том, чтобы отслеживать два итератора. На каждом шаге сравнивайте первые элементы диапазонов. Если они равны, добавьте элемент в пересечение и продвиньте оба итератора вперед. Если первое меньше второго, то продвигайте первый итератор. Если первый элемент больше, то продвиньте второй итератор. Это выполняется во времени O (n), поскольку каждая итерация потребляет по крайней мере один элемент, и всего O (n) элементов в целом.

Ответ 2

Интересно, что никто не упоминал хэш-таблицу.
Независимо от вашей реализации набора (даже если "set" здесь означает простой массив), вы можете

помещает содержимое первого набора в хэш-таблицу и
повторить второй набор, проверив, содержит ли хэш-таблицу текущий элемент.

O(n)

Ответ 3

intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

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

Ответ 4

Объедините два массива и подсчитайте количество вхождений каждого элемента в этом объединенном массиве и поместите их в новый массив. Затем проверьте этот массив count для записей, содержащих 2, эти элементы находятся в пересечении двух наборов.

Ответ 5

Для всех элементов в наборе 1: проверьте, находится ли этот элемент в наборе 2. Вы можете реализовать набор, который имеет амортизированное время поиска O (1).

Ответ 6

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

FUNCTION: INTERSECTION ( LIST A, LIST B )
{
   CREATE C AS EMPTY LIST

   FOR EVERY: NUMBER n IN A
   {
        IF BINARY-SEARCH(n) IN B
        {
            ADD n TO C
        }
   }

   RETURN C
}

Time Complexity = O(n O(BINARY-SEARCH)) = O(n log n)

если список B равен hashed, то мы имеем BIG-THETA(C n + T(hash))

где BIG-THETA - асимптотическое среднее, а C - constant и T(hash) требуется время для хэш-функции