Есть ли алгоритм, который, учитывая два набора, вычисляет их пересечение в линейном времени?Вычисление множества пересечений в линейном времени?
Я могу запустить две циклы for, чтобы проверить все пары элементов, элементы записи, которые я нахожу в обоих наборах. Однако время выполнения будет равно O (n). Как это сделать в O (n) времени?
Для всех элементов в наборе 1: проверьте, находится ли этот элемент в наборе 2. Вы можете реализовать набор, который имеет амортизированное время поиска O (1).
Альтернативный вариант, если вы используете набор на основе сортированного дерева вместо хэш-метода: Итерации по обоим наборам в отсортированном порядке, переход к следующему элементу текущего «самого низкого» набора. O (n) в общем количестве элементов. –
intersection(a, b):
result = new empty set
for x in b:
if a contains x:
add x to result
return result
Если тест contains является постоянная время (например, в наборе, который использует хэш-таблицу в качестве реализации), то этот алгоритм O(n).
Если a и b являются одинаковыми наборами, тогда алгоритм принимает O (n^3) время, так как поиск в «b» и добавление элемента к «результату» занимает O (n) время. Добавление элемента к набору на основе массива принимает время O (n), поскольку наборы не могут иметь дублированный элемент. Проверка дублирования выполняется при каждом добавлении. Если результат и b основаны на хеш-таблице, то даже если вы не можете быть уверены, что поиск и добавление занимает время O (1), он может также принимать O (n). – Viplime
Это зависит от реализации вашего набора.
Если у вас есть хеш-набор (O (1) поиск), то подход, обозначенный всеми другими плакатами, верен. Итерации по всем элементам в первом наборе. Если он находится во втором наборе, добавьте его в результат. Это выполняется в O (n) времени.
Если у вас есть набор деревьев (O (lg n)), то этот подход будет работать, но он работает в O (n lg n) времени. Ты можешь лучше; существует O (n) решение. Я предполагаю, что у вас есть своего рода итератор, который может пересекать элементы двух наборов в порядке возрастания. Если вы это сделаете, тогда вопрос будет «задан двумя списками в отсортированном порядке, найдите их пересечение». Это можно сделать, используя модифицированную версию алгоритма, который вы используете для объединения двух диапазонов. Идея состоит в том, чтобы отслеживать два итератора. На каждом шаге сравнивайте первые элементы диапазонов. Если они равны, добавьте элемент в пересечение и продвиньте оба итератора вперед. Если первое меньше второго, то продвигайте первый итератор. Если первый элемент больше, то продвиньте второй итератор. Это выполняется во времени O (n), потому что каждая итерация потребляет по крайней мере один элемент, и всего всего O (n) элементов.
Два набора не отсортированы. Что если я использую метод сортировки слияния, а затем следую вашему методу сравнения первых элементов диапазонов, но я не уверен, что он будет работать в O (n). Сорт bcoz-merge принимает O (nlogn) время – NEO
Если вы поместили наборы в порядке сортировки по времени O (n lg n), этот метод должен работать, но он не будет работать в линейном времени из-за служебных данных сортировки. Как представлены ваши наборы? – templatetypedef
Наборы находятся в массиве. – NEO
Интересно, что никто не упоминал хеш-таблицу.
Независимо от реализации множества (даже если «множество» здесь означает простой массив), вы можете
O(n)
, если один из двух списков упорядочен, то мы можем начать с неупорядоченным списком
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)
если список Б hashed, то мы в BIG-THETA(C n + T(hash))
где BIG-THETA - это асимптотика ушные среднем и C это время constant и T(hash) необходим для хэш-функции
Объединить два массива и подсчитать не появлений каждого элемента в этом массиве комбинированного и поместить их в новый массив. Затем проверьте этот массив count для записей, содержащих 2, эти элементы пересекаются с двумя наборами.
ПОЧЕМУ когда-либо было n^2? Разве это не «очевидное» решение в O (n), и мы должны пытаться найти лучший? – pete