Перейти к содержанию

4.6. Сравнение со сортировкой

Во многих задачах один и тот же результат можно получить разными путями:

  • используя структуры данных (множества, хеш‑таблицы и т. п.);
  • используя сортировку и линейный проход.

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

Задача-пример: сколько общих элементов у двух списков

Даны два списка (или массива) A и B, каждый длины n. Нужно посчитать, сколько значений встречается и там, и там.

Пример:

  • A = [7, 1, 6, 10, 3]
  • B = [4, 1, 10, 7]

Ответ: 3, потому что общие элементы — 1, 7 и 10.

Наивное решение — проверить все пары элементов — работает за O(n^2) и быстро становится слишком медленным. Дальше рассмотрим более быстрые подходы.

Алгоритм 1: упорядоченное множество (set)

  1. Добавим все элементы списка A в структуру set (обычно это сбалансированное дерево).
  2. Пройдём по B и для каждого элемента проверим, есть ли он в set.

Поскольку операции insert/find в set работают за O(log n), итог:

  • построение множества: O(n log n)
  • проверки элементов B: O(n log n)

Итого: O(n log n).

Плюс: элементы в set хранятся в отсортированном порядке.

Минус: структура сложнее (дерево), и из-за этого константы часто ощутимы.

Алгоритм 2: хеш‑множество (unordered_set)

Здесь делаем то же самое, но используем unordered_set (хеш‑таблица):

  1. Загружаем A в unordered_set.
  2. Для каждого элемента из B проверяем наличие.

В среднем insert/find работают за O(1), поэтому:

Итого: O(n) в среднем.

Плюс: обычно существенно быстрее дерева.

Минусы:

  • порядок элементов не хранится;
  • в редких случаях возможны «плохие» входы, когда из-за коллизий время может деградировать (в реальной практике на соревнованиях это обычно не проблема, но помнить стоит).

Алгоритм 3: сортировка + два указателя

Вместо структур данных можно:

  1. Отсортировать A и B.

  2. Пройти по ним одновременно двумя указателями (как в «слиянии»):

  3. если A[i] == B[j] — нашли общий элемент, увеличиваем счётчик и двигаем оба указателя;

  4. если A[i] < B[j] — двигаем i;
  5. иначе двигаем j.

Сортировки занимают O(n log n), проход — O(n), значит итог:

O(n log n).

Зато после сортировки остаётся очень простой и быстрый линейный проход.

Сравнение скорости на практике

Если элементы списков — случайные целые числа (например, из диапазона 1 … 10^9), то на современном компьютере типичная картина может выглядеть так:

n Алг. 1 (set) Алг. 2 (unordered_set) Алг. 3 (sorting)
10^6 1.6 s 0.35 s 0.22 s
2·10^6 3.9 s 0.9 s 0.35 s
3·10^6 6.0 s 1.4 s 0.55 s
4·10^6 8.1 s 1.9 s 0.75 s
5·10^6 10.4 s 2.6 s 0.95 s

Что видно:

  • Алгоритмы 1 и 2 отличаются только выбором структуры данных, но unordered_set может быть в 4–5 раз быстрее, потому что у дерева дорогие операции и указатели, а хеш‑таблица обычно проще.

  • Самым быстрым оказывается Алгоритм 3 (сортировка). Хотя его асимптотика O(n log n), он часто выигрывает за счёт того, что:

  • сортировка реализована крайне оптимизировано;

  • дальнейший проход — простой линейный цикл с хорошей локальностью памяти.

Вывод

В задачах на пересечения/подсчёты совпадений часто стоит помнить про альтернативу:

  • unordered_set — отличный быстрый «универсальный» вариант.
  • сортировка + два указателя — иногда ещё быстрее, особенно если после сортировки можно решить задачу почти полностью линейным проходом.
  • set полезен, когда нужен порядок (например, ближайший элемент, lower_bound и т. п.), но ради одной проверки «есть/нет» он нередко проигрывает по времени.