Блог

У меня есть миллион двоичных последовательностей ,они одинаковой длины, например (1000010011,1100110000….) и так далее. И я хочу знать, сколько у них разных групп(одни и те же последовательности принадлежат к одной и той же группе ).каков самый быстрый способ? Не стой, пожалуйста.

В зависимости от длины L последовательности:

L
Это достаточно мало по сравнению с размером ввода. Набор ведер с L ведрами-это все, что вам нужно. — предварительно выделите массив размером 2 ^L, так как у вас ~миллион последовательностей, а 2 ²⁰-это ~миллион, вам понадобится только O(n) дополнительной памяти.

• Пройдите через свою последовательность, отсортируйте по ведрам
• Пройдитесь по ведрам, подсчитайте результаты. Верните их.
• И мы закончили.

Временная сложность будет O(n) при O(n) стоимости памяти. Это оптимально с точки зрения сложности, так как вы все равно должны посетить каждый элемент хотя бы один раз, чтобы проверить его значение.

L достаточно большой: хэш-таблица
Если вы выберете разумную функцию хеширования и хороший размер хэш-таблицы(или словаря, если нам нужно сохранить подсчеты)¹, у вас будет небольшое количество коллизий при вставке. Амортизированное время будет равно O(n), так как, если хэш хороший, то вставка амортизируется O(1).
В качестве примечания, сортировка по корзинам технически является идеальным хэшем, поскольку хэш-функция в этом случае является функцией один к одному.

L неоправданно большое: двоичное дерево
если по какой-то причине построение хэша невозможно или вы хотите обеспечить согласованность, то можно создать двоичное дерево для хранения значений.
Для этого потребуется O(nlog(n)), как обычно делают двоичные деревья.

¹ ~2 м должно быть достаточно, и это все еще O(n). Может быть, вы могли бы опуститься еще ниже, примерно до 1,5 м размера.