Разделение проще, чем сортировка?

Ответ 1

Кажется, вы задаете два разных вопроса: "

1) Если разрешить только проверки равенства, облегчит ли раздел, чем если бы у нас был некоторый порядок? Ответ - нет. Вам нужно сравнить Omega (n ^ 2), чтобы определить разбиение в худшем случае (все разные, например).

2) Если разрешить упорядочение, проще разбиение на разделы, чем сортировка? Ответ снова - нет. Это связано с Проблема отличия элемента. Который говорит, что для того, чтобы даже определить, все ли объекты различны, вам нужны сравнения Omega (nlogn). Поскольку сортировка может выполняться в O (nlogn) времени (а также с нижними границами Omega (nlogn)) и решает проблему раздела, асимптотически они одинаково трудны.

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

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

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

Другие ответы также, похоже, забывают, что ваш вопрос (в основном) о сравнении разбиения и сортировки!

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

--- EDIT: ---

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

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

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