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

Question

Это вопрос, который долго не давал мне покоя ...

Предположим, у меня есть список предметов и отношение эквивалентности к ним, и сравнение двух предметов занимает постоянное время.Я хочу вернуть раздел элементов, например, список связанных списков, каждый из которых содержит все эквивалентные элементы.

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

Но можно ли сделать это более эффективно, чем с помощью сортировки?Является ли временная сложность этой проблемы ниже, чем сложность сортировки?Если нет, то почему?

Answer 1

Вы, кажется, задаете два разных вопроса за один раз.

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

--- РЕДАКТИРОВАТЬ: ---

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

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