Что касается сложности (если используется алгоритм сортировки на основе сравнения)

Question

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

но, как мы все знаем, проблема голландского флага может сортировать 3 различных элемента (многократно используемых) за время O (n). Он также основан на модели сравнения, но может сортировать за время O (n). так как же мы можем обосновать нижнюю границу сортировки на основе модели сравнения, потому что проблема голландского флага вроде бы нарушает это.

Пожалуйста, помогите мне понять разницу .....

Спасибо

Answer 1

По моему мнению, это не является существенным «противоречием» нижней границы, потому что это частный случай (возможный диапазон значений меньше, чем общее количество элементов, фактически это константа, 3) который можно использовать для нахождения алгоритма быстрее, чем O (N * logN), который является нижней границей для общего алгоритма сортировки на основе сравнения (т. е. когда у вас нет информации о содержании последовательности).

Как правило, в случае, когда N элементов находятся в диапазоне 0..K с K

Answer 2

Граница Omega(n log n) дает нижнюю границу для сортировки на основе сравнения произвольных элементов.

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

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

Answer 3

Дело в том, что набор голландских флагов не полностью упорядочен. Есть много равных элементов, фактически, когда вы подсчитываете различные объекты, это набор (максимум) размера 3.

Граница Omega(n log n), вероятно, является жесткой, только если для объектов a и b выполняется a<b или b>a (иначе: все объекты различны )

На самом деле, я могу отсортировать по O(0), когда все объекты должны быть null.

Предполагая, что есть как минимум два различных объекта, я считаю, что правильная граница - это что-то вроде Omega(n log m), где n - это число объектов, а m - это число различных объектов ( которые не сортируются равными). Проще говоря, log m - это количество решений, необходимых для поиска выходного сегмента. В общем случае, O(log m)=O(log n), если количество равных объектов мало. В проблеме голландского флага m=3.

Radix sort использует это по-другому. Он также считается линейным. Тем не менее, требуется log m передачи данных, где m - число возможно различных элементов. Таким образом, сортировка Radix также имеет вид Omega(n log m), где m - количество объектов, которые она может различить.

Answer 4

Проблема голландского флага - это скорее алгоритм разделения.

Это только первый шаг к сортировке. Вы можете использовать его для сортировки (применяя его к разделам снова и снова), но я думаю, что в итоге вы получите Omega (nlogn).

Знание количества различных значений (3 в случае флага) и их значений (синий, белый, красный) - очень редкий случай.

Answer 5

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