@Mercury13
Программист на «си с крестами» и не только

Нахождение пересечения std::map’ов быстрее, чем O(|A| + |B|)?

Есть два std::map’а с одинаковой операцией «меньше». Пройти по всем элементам, которые есть в том и другом.

Возможны любые соотношения между map’ами — и первый намного больше второго, и второй намного больше первого, и один гарантированно вкладывается во второй.

Физическая сборка пересечения не обязательна, хватает прохода по лямбда-функции.

Можно ли, используя функции стандартной библиотеки Си++, получить сложность, например, O(|A ∩ B| log max{|A|, |B|})?
  • Вопрос задан
  • 143 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы