Действительно ли разделение легче, чем сортировка?

Если необходимо использовать компаратор, то нижняя граница равна Ω (n log n) сравнений для сортировки или разделения. Причина в том, что все элементы должны быть проверены Ω (n), и компаратор должен выполнить log n сравнений для каждого элемента, чтобы однозначно идентифицировать или разместить этот элемент по отношению к другим (каждое сравнение делит пространство на 2, и поэтому для пробела размера n, требуется log n сравнений.)

Если каждый элемент может быть связан с уникальным ключом, полученным за постоянное время, то нижняя граница равна Ω (n) для сортировки муравьиного разбиения (см. RadixSort )

Сортировка на основе сравнения обычно имеет нижнюю границу O(n log n).

Предположим, что вы итерируетесь над своим набором элементов и помещаете их в ведра с элементами с одинаковым сравнительным значением, например, в набор списков (скажем, используя хэш-набор). Эта операция явно O(n), даже после извлечения списка списков из множества.

--- EDIT: ---

Это, конечно, требует двух предположений:

• Существует хэш-алгоритм с постоянным временем для каждого элемента, подлежащего разбиению.
• Количество ведер не зависит от объема входных данных.

Таким образом, нижняя граница разбиения равна O(n).

Разбиение на разделы быстрее, чем сортировка, в целом, потому что вам не нужно сравнивать каждый элемент с каждым потенциально эквивалентным уже отсортированным элементом, вам нужно сравнивать его только с уже установленными ключами вашего разбиения. Внимательно рассмотрите radix sort. Первый шаг радиксной сортировки заключается в разбиении входных данных на основе некоторой части ключа. Радиксная сортировка - это O(kN). Если ваш набор данных имеет ключи, ограниченные заданной длиной k, вы можете отсортировать его O(n). Если ваши данные сравнимы и не имеют ограниченного ключа, но вы выбираете ограниченный ключ для разбиения набора, сложность сортировки набора будет O(n log n), а разбиения - O(n).

Это классическая проблема в структурах данных, и да, это проще, чем сортировка. Если вы хотите также быстро найти, к какому набору принадлежит каждый элемент, вам нужна структура данных непересекающегося набора вместе с операцией поиска объединения. См. Здесь: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

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

Без хэш-функции вам пришлось бы сравнивать каждый новый элемент, который нужно вставить в разделенные списки, с заголовком каждого существующего списка. Эффективность этой стратегии зависит от того, сколько разделов в конечном итоге будет.

Допустим, у вас есть 100 элементов, и они в конечном итоге будут разделены на 3 списка. Затем каждый элемент нужно будет сравнить не более чем с 3 другими элементами, прежде чем вставлять его в один из списков.

Однако, если эти 100 элементов в конечном итоге будут разделены на 90 списков (т.е. очень мало эквивалентных элементов), это совсем другая история. Теперь ваше время выполнения ближе к квадратичному, чем к линейному.

Если вас не волнует окончательный порядок наборов эквивалентности, то разделение на наборы эквивалентности может быть быстрее. Однако это зависит от алгоритма и количества элементов в каждом наборе.

Если в каждом наборе очень мало элементов, то вы можете просто отсортировать элементы, а затем найти соседние равные элементы. Хороший алгоритм сортировки - O (n log n) для n элементов.

Если есть несколько наборов с большим количеством элементов в каждом, вы можете взять каждый элемент и сравнить с существующими наборами. Если он принадлежит к одному из них, добавьте его, в противном случае создайте новый набор. Это будет O (n * m), где n - количество элементов, а m - количество наборов эквивалентности, которое меньше O (n log n) для больших n и малых m, но хуже, поскольку m стремится к n .

Комбинированный алгоритм сортировки / разделения может быть быстрее.

Время, необходимое для выполнения возможно несовершенного раздела с использованием хеш-функции, будет O (n + bucketcount) [не O (n * bucketcount)]. Делать счетчик ведра достаточно большим, чтобы избежать всех коллизий, будет дорого, но если хеш-функция работает вообще хорошо, в каждом ведре должно быть небольшое количество различных значений. Если можно легко сгенерировать несколько статистически независимых хэш-функций, можно взять каждую корзину, ключи которой не все совпадают с первой, и использовать другую хеш-функцию для разделения содержимого этой корзины.

Предполагая постоянное количество сегментов на каждом шаге, время будет O (NlgN), но если установить количество сегментов примерно как sqrt (N), среднее количество проходов должно быть O (1 ) и работа в каждом проходе O (n).