Нахождение пересечения std::map’ов быстрее, чем O(|A| + |B|)?
Есть два std::map’а с одинаковой операцией «меньше». Пройти по всем элементам, которые есть в том и другом.
Возможны любые соотношения между map’ами — и первый намного больше второго, и второй намного больше первого, и один гарантированно вкладывается во второй.
Физическая сборка пересечения не обязательна, хватает прохода по лямбда-функции.
Можно ли, используя функции стандартной библиотеки Си++, получить сложность, например, O(|A ∩ B| log max{|A|, |B|})?
Без потери общности примем меньшее множество за A, а большее соответственно за B, поскольку размер множества можно определить за O(1).
Поиск одного элемента в B занимает O(log|B|), всего поисков будет |A|, итого общая оценка O(|A|log|B|).
Отсюда вопрос, а чего собственно вы хотите? :)
В принципе вы можете использовать структуру Disjoint Set Union, она позволяет за амортизированное O(1) проверять в какое множество входит элемент, но таких проверок всё равно понадобится O(|A|).
Ещё можно использовать какие-нибудь методы предпросчёта, например такой: пусть у нас всего N множеств, заведем матрицу NxN, в ячейке (i, j) находится множество, совпадающее с пересечением множеств i и j, оценка на время вставки и удаления O(N), на выписывание пересечения O(|N_i ∩ N_j|). На память O(N^2 * max(|N_i|))
