пересечение n векторов

Question

Я новичок в программировании, и я недавно столкнулся с проблемой поиска пересечения n векторов (int векторов), которые отсортировали ints. Подход, который я придумал, имеет сложность O (n^2), и я использую функцию std :: set_intersect.

Подход, к которому я пришел, состоит из двух векторов: первый вектор будет соответствовать первому вектору, который у меня есть, а второй будет вторым вектором. Я вызываю set-пересечение на двух и переписываю на первый вектор, затем использую функцию clear clear на второй. Затем я переписываю следующий вектор во второй и повторяю процесс и в конечном итоге возвращаю первый вектор.

Я действительно верю, что есть более эффективный способ обойти это, но на данный момент я не могу придумать более эффективную манеру. Любая помощь по этому вопросу будет высоко оценена.

Answer 1

К счастью, я думаю, что более сложная привязка может быть поставлена ​​на сложность вашего алгоритма .

Сложность std::set_intersection на входных наборах размеров n1 и n2 равна O (n1 + n2). Вы можете взять свои оригинальные векторы и пересечь их в одноименном стиле , т. Е. В первом раунде вы пересечете 1-й и 2-й векторы , 3-й и 4-й, 5-й и 6-й и т. Д .; на второй круг вы пересекаете 1-й и 2-й пересечения, 3-й и 4-й, и так далее; повторяйте, пока последний раунд не произведет только одно пересечение. Сумма размеров всех векторов, выживших в каждом раунде, составляет не более половину суммы размеров векторов в начале раунда, , поэтому этот алгоритм принимает время O (N) (также O (N) пространство) всего где N - сумма размеров всех исходных векторов на вашем входе. (это O (N), так как N + N/2 + N/4 + ... < 2н.)

Таким образом, учитывая вход, состоящий из уже отсортированных векторов, сложность алгоритма O (N).

Ваш алгоритм объединяет векторы в совершенно другой последовательности, , но пока я не уверен на 100%, это также O (N), я сильно подозреваю, что это так.

---

Edit: относительно того, как на самом деле осуществить «турнир» алгоритм в C++, это зависит от того, насколько сильно вы хотите работать, чтобы оптимизировать это, и несколько от характера вашего входа.

Самый простой подход - создать новый список векторов; возьмите два вектора из старого списка, вставьте вектор в новый список, объедините два старых вектора на новый вектор, уничтожьте старые векторы, надейтесь, что библиотека эффективно управляет памятью.

Если вы хотите уменьшить выделение новых векторов, то повторное использование векторов (как вы уже думали) может помочь. Если структура входных данных равна , например, std::list<std::vector<int> >, вы можете начать с нажатия одного пустого вектора на передний край этого списка. Сделайте три итератора, один для нового вектора и один для каждого из первых первых двух векторов в списке. Возьмите пересечение векторов на последних двух итераторах, , записывая результат на первый итератор, затем очистите векторы на последних двух итераторах . Переместите два последних итератора вперед по двум местам, переместите первый итератор вперед на одно место. Повторение. Если вы достигнете состояния, в котором один из двух последних итераторов достиг конца(), а другой не имеет, стирает все элементы списка между первым итератором и другим итератором. Теперь у вас есть список векторов снова и можно повторить, пока есть более одного вектора в списке.

Если вход std::vector<std::vector<int> > убирания элемент на передней части списка является относительно дорогим, так что вы можете захотеть немного более сложный алгоритм. Есть много вариантов, нет действительно очевидных победителей, о которых я могу думать.

Answer 2

Вот еще один анализ, который показывает, что ваш алгоритм уже линейный.

Предположим, что у вас есть набор векторов, и алгоритм многократно выбирает два вектора из коллекции и заменяет их своим пересечением, пока не останется один вектор. Ваш метод подходит для этого описания. Я утверждаю, что любой такой алгоритм будет тратить, в общем, линейное время во всех исполнениях set_intersection.

Предположим, что set_intersection занимает не более A * (x + y) операций по векторам величин x и y.

Позвольте K быть суммой длин всех векторов в коллекции. Он начинается с размера ввода (n), и он не может опускаться ниже нуля, поэтому он может измениться не более чем на n.

Каждый раз, когда векторы размеров (x, y) объединяют значение K уменьшается, по меньшей мере, (x + y)/2, как результат должен быть короче, чем любой из входных данных. Если мы суммируем это по всем звонкам, получим, что sum { (x + y)/2 } <= n, так как K не может измениться более чем на n.

Из этого можно выделить sum { A * (x + y) } <= 2 * A * n = O(n). Левая сторона здесь - общее время, проведенное в set_intersection.

В менее формальном языке - провести x + y время в set_intersection вам нужно удалить, по крайней мере (x + y)/2 элементы из вашей коллекции, так что тратить больше, чем линейное время выполнения set_intersection бы вы бежите из элементов.